Timeline for possible degree sequences for a graph with multiple edges but no loops
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 27, 2016 at 17:30 | history | edited | Michael Hardy | CC BY-SA 3.0 |
edited body
|
| S Oct 27, 2016 at 13:42 | history | suggested | Martin Sleziak | CC BY-SA 3.0 |
changed MathJax to Markdown for italics
|
| Oct 27, 2016 at 12:51 | review | Suggested edits | |||
| S Oct 27, 2016 at 13:42 | |||||
| Oct 27, 2016 at 12:47 | comment | added | Martin Sleziak | Cross-posted also on math.SE: math.stackexchange.com/questions/1986944/… | |
| Oct 27, 2016 at 8:17 | history | edited | Alex | CC BY-SA 3.0 |
deleted 34 characters in body
|
| Oct 27, 2016 at 8:15 | comment | added | Alex | @FedorPetrov You're right. In the normal definition of degree sequences one does not delete vertices. But it seems awfully close in flavour. I shall edit my post accordingly. | |
| Oct 27, 2016 at 7:34 | comment | added | Fedor Petrov | For simple graphs it is Erdös - Gallai theorem - why? They seem to consider sequence of degrees in the initial graph, without removing vertices. | |
| Oct 27, 2016 at 4:42 | comment | added | Włodzimierz Holsztyński | indeed, one could make this lexicographic decision or one may consider more than one variation of your question. The other variant would call for a study of all sequences obtained by removals of arbitrary maximal vertices (one at the time, of course). | |
| Oct 27, 2016 at 3:41 | comment | added | Alex | If more than one vertex has maximal degree then for each vertex $v$ of maximal degree consider the graph $G_v=G\setminus\{v\}$ and calculate its degree sequence $D_v$. Then compare the $D_v$s lexicographically and choose the $v$ with the highest $D_v$. | |
| Oct 27, 2016 at 3:32 | comment | added | Włodzimierz Holsztyński | There can be more than one vertex with a maximal degree. Then what next? | |
| Oct 27, 2016 at 3:08 | history | asked | Alex | CC BY-SA 3.0 |