Timeline for What's the name of graphs with each vertex contained in a cycle?
Current License: CC BY-SA 2.5
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 7, 2012 at 13:44 | comment | added | László Kozma | @Hans: the opposite direction is not true, it can be that every vertex is in a cycle, but not every edge is in a cycle. Example: two cycles connected with a bridge. | |
| Nov 5, 2012 at 19:31 | comment | added | David Eppstein | Yes, for connected graphs, every edge belonging to a cycle implies every vertex belonging to a cycle. It's also true more generally for graphs without isolated vertices regardless of connectivity. This is trivial: just find an edge adjacent to the given vertex and look for a cycle through that edge. | |
| Oct 29, 2012 at 19:24 | comment | added | Hans-Peter Stricker | Ok, you are right. But if I restricted myself to connected graphs? | |
| Oct 29, 2012 at 18:28 | comment | added | David Eppstein | A graph in which each edge belongs to a cycle could still have isolated vertices. | |
| Oct 29, 2012 at 18:17 | comment | added | Hans-Peter Stricker | @David: If every edge is contained in a cyle, doesn't every vertex have to be contained in a cycle, too? And vice versa? That is, isn't the concept "self-dual"? | |
| Jan 11, 2010 at 2:21 | comment | added | Hans-Peter Stricker | I guess it was not (if you refer to the "fruits" of "trees"). But can you - who has used the term "unreasonable" too (in another context) - appreciate the question? | |
| Jan 11, 2010 at 1:56 | comment | added | Qiaochu Yuan | Nice pun! Was it intentional? | |
| Jan 11, 2010 at 0:52 | comment | added | Hans-Peter Stricker | If this graph property was fruitless: How could this be explained, compared to the "unreasonable" fruitfulness of trees? | |
| Jan 11, 2010 at 0:48 | comment | added | Hans-Peter Stricker | Could this mean that this is an unfruitful concept (since if it were fruitful it would have a name X, e.g. to be able to formulate statements like "all graphs that are X are Y" or vice versa?) The other way round: Do you know an interesting theorem which implies graphs with the above mentioned property? | |
| Jan 11, 2010 at 0:38 | history | answered | David Eppstein | CC BY-SA 2.5 |