Timeline for Construct a non-connected graph with a given degree sequence
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 12, 2019 at 21:31 | history | edited | Szabolcs Horvát | CC BY-SA 4.0 |
added 246 characters in body
|
| May 12, 2019 at 19:23 | vote | accept | Szabolcs Horvát | ||
| May 12, 2019 at 19:05 | answer | added | John Machacek | timeline score: 6 | |
| May 12, 2019 at 16:55 | history | edited | Szabolcs Horvát | CC BY-SA 4.0 |
added 765 characters in body
|
| May 12, 2019 at 16:42 | comment | added | Szabolcs Horvát | @GerhardPaseman I was thinking along the same lines, but this is still far from a systematic way (i.e. an algorithm). Once you create a clique, it's not even clear if the remaining degrees can be wired up to form a simple graph (and deciding this is a highly non-trivial problem). | |
| May 12, 2019 at 15:50 | comment | added | Gerhard Paseman | Start by forming and removing large dangling cliques. In your first case, the largest clique possible is a triangle. Picking the three largest degrees, this leaves an extra edge. You have a degree 1 vertex, so use it. You now have one component. In the second case, the largest clique possible is an edge. Picking the two largest degrees, that leaves four edges, which you have to use on all remaining vertices. Gerhard "Is Liking Maximal Cliques Today" Paseman, 2019.05.12. | |
| May 12, 2019 at 14:40 | history | asked | Szabolcs Horvát | CC BY-SA 4.0 |