Timeline for Minimize edge number under diameter and max-degree constraint
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 19, 2018 at 14:39 | comment | added | Gerhard Paseman | I am not a graph theorist and do not know the literature, so I have no references for you right now. Except for the case of n-1 edges, there is no guarantee on the minimum number of edges. However, this shows that d has to be greater than 2 and less than log n in order for finding the minimum number of edges to be a challenge, when given k as a restriction. For searching, the only non-obvious suggestion I have is to try literature on computer networking. Gerhard "Surely Someone Did This Already" Paseman, 2018.09.19. | |
| Sep 19, 2018 at 12:16 | comment | added | TheRacoonOfDeath | Thank you for your answer. Is this construction guaranteed to lead to the graph with the minimum number of edges? Are there references you can recommend? | |
| Sep 14, 2018 at 17:12 | history | edited | Gerhard Paseman | CC BY-SA 4.0 |
added 174 characters in body
|
| Sep 14, 2018 at 17:07 | history | answered | Gerhard Paseman | CC BY-SA 4.0 |