Wikipedia:Reference desk/Archives/Mathematics/2021 November 19
| 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
editgraph diameter problem
editI 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)
- See degree diameter problem. --116.86.4.41 (talk) 06:27, 19 November 2021 (UTC)
- 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)
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)