Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
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 '10 at 1:34
add comment

5 Answers 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.

share|improve this answer
    
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 '10 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 '10 at 0:52
6  
Nice pun! Was it intentional? –  Qiaochu Yuan Jan 11 '10 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 '10 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 '12 at 18:17
show 4 more comments

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.

share|improve this answer
    
Thanks. Please see my comments to David's answer. They apply also to yours. –  Hans Stricker Jan 11 '10 at 1:07
    
How can vertices of G-v be adjacent to v? –  Hans Stricker Jan 11 '10 at 1:10
    
Sorry, I meant adjacent in the original graph. –  Harrison Brown Jan 11 '10 at 1:16
    
Sorry for my part, I should have understood it this way. (You treat the one counter-example of David below - the 8-graph - and we are done?) –  Hans Stricker Jan 11 '10 at 1:24
add comment

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

share|improve this answer
    
+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 '10 at 7:27
add comment

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.

share|improve this answer
add comment

2-connected or biconnected

share|improve this answer
    
of course, this works only for connected graphs. –  Klingonesque Jan 11 '10 at 0:32
    
A figure-eight graph has every vertex in a cycle but is not biconnected. –  David Eppstein Jan 11 '10 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 '10 at 0:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.