Timeline for Small degree vertices in an epsilon-tough graph
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 14, 2015 at 13:57 | history | edited | Daniel Soltész | CC BY-SA 3.0 |
Motivated the question.
|
| Jul 5, 2015 at 0:46 | comment | added | Daniel Soltész | It is indeed not minimal, you can delete an edge of the identified point and the resulting graph is still $m$-tough. The minimally $m$-tough subgraph in your graph is a star-like tree but with longer paths instead of the leaves. | |
| Jul 4, 2015 at 23:37 | comment | added | The Masked Avenger | I'm still getting my head around the definition. Anyway, take m = 1/epsilon many disjoint cycle graphs of diameter > 2 , and pick a point on each cycle and identify all those m points to get an m petalled flower graph. Does this help with the question? (I'm unsure if it is minimal.) | |
| Jul 4, 2015 at 14:01 | history | asked | Daniel Soltész | CC BY-SA 3.0 |