Mathematics desk
< November 18	<< Oct \| November \| Dec >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 19[edit]

graph diameter problem[edit]

I wonder how much is known about this question: For a given number of vertices of given maximum degree, what graph has the smallest diameter? What if the graph is directed and antisymmetric? —Tamfang (talk) 06:06, 19 November 2021 (UTC)[reply]

See degree diameter problem. --116.86.4.41 (talk) 06:27, 19 November 2021 (UTC)[reply]

Not quite the same problem – maximize |V| given d,k, versus minimize d given k,|V|. But it leads to Table of the largest known graphs of a given diameter and maximal degree, which is relevant to what I was thinking about, so thanks. —Tamfang (talk) 03:26, 20 November 2021 (UTC)[reply]

Try cstheory.stackexchange.com if you're still looking for help with this. I don't see the answer off the top of my head. It wouldn't surprise me if it's NP-hard. 2602:24A:DE47:B8E0:1B43:29FD:A863:33CA (talk) 08:35, 22 November 2021 (UTC)[reply]