Welcome to MathOverflow

Question

7

A tree is a graph with no vertex contained in a cycle.

A non-tree is a graph with some vertex contained in a cyle.

What's the name of graphs with each vertex contained in a cycle?

edited Jan 11 2010 at 9:51

Steven Sam
5,270●1●16●35

asked Jan 11 2010 at 0:29

Hans Stricker
5,233●12●38

1

I'm wondering why no one had voted up this question (until I just did), even though people were answering and voting up answers. – Jonas Meyer Jan 11 2010 at 1:34

David Eppstein · Answer 1 · 2010-01-11 00:38:29Z UTC

5

Undirected graphs in which every edge is contained in a cycle are called bridgeless or 2-edge-connected. But I don't know of a word for the analogous concept for vertices.

answered Jan 11 2010 at 0:38

David Eppstein
9,233●1●21●41

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? – Hans Stricker Jan 11 2010 at 0:48

If this graph property was fruitless: How could this be explained, compared to the "unreasonable" fruitfulness of trees? – Hans Stricker Jan 11 2010 at 0:52

6

Nice pun! Was it intentional? – Qiaochu Yuan Jan 11 2010 at 1:56

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? – Hans Stricker Jan 11 2010 at 2:21

@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"? – Hans Stricker Oct 29 at 18:17

show 4 more comments

Harrison Brown · Answer 2 · 2010-01-11 01:45:44Z UTC

I don't know a name, but I'll give you a different characterization. Biconnectivity is sufficient but too strong, while "having minimum degree at least 2" is necessary but too weak. I'm almost certain this is a necessary and sufficient condition:

$G$ has minimum degree at least 2, and if v is a cutvertex of $G$, then there is some new connected component of $G - v$ with at least two vertices adjacent to v.

Here's a proof of sufficiency: If v is not a cutvertex of $G$, then pick any two vertices adjacent to v. There's a path between them not going through v (since $G - v$ is connected), so v is contained in a cycle.

If v is a cutvertex of $G$, then pick the two vertices adjacent to v that are in the same connected component of $G - v$. There's a path between them that extends to a cycle containing v.

Now, a proof of necessity. Suppose that $G$ has a cutvertex $v$ whose removal does create deg(v)-1 new connected components. Then $v$ can't lie in a cycle. (This is easy to check.)

This characterization is equivalent to: Removing any vertex of degree d increases the total number of connected components by at most $d-2$. Some generalization of this property may have a name.

Douglas S. Stones · Answer 3 · 2010-01-25 04:40:25Z UTC

3

These are the graphs that admit "vertex cycle covers". http://en.wikipedia.org/wiki/Vertex_cycle_cover

answered Jan 25 2010 at 4:40

Douglas S. Stones
2,956●1●12●31

+1, even if this is not really a name but just another characterization. (At least it's something to google for.) – Hans Stricker Jan 25 2010 at 7:27

Tony Huynh · Answer 4 · 2010-02-18 00:26:09Z UTC

Assuming that $G$ is connected, we can get a characterization by looking at the block decomposition $B(G)$ of $G$ into 2-connected pieces. That is, we simply look at which vertices of $B(G)$ are $K_2$'s. The required characterization is:

Every vertex of $G$ is contained in a block of $G$ which is not a $K_2$.

Of course, this is the same answer as Harrison's, but it gives a more global view. Also, necessity and sufficiency are trivial.

Klingonesque · Answer 5 · 2010-01-11 00:31:54Z UTC

-2

2-connected or biconnected

answered Jan 11 2010 at 0:31

Klingonesque
21●4

	of course, this works only for connected graphs. – Klingonesque Jan 11 2010 at 0:32
	A figure-eight graph has every vertex in a cycle but is not biconnected. – David Eppstein Jan 11 2010 at 0:36
	Even if those graphs were biconnected, their biconnectivity would have to be proved, but would not be the defining property, for which I am looking for a name. – Hans Stricker Jan 11 2010 at 0:55

What’s the name of graphs with each vertex contained in a cycle?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

5 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.