10
$\begingroup$

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?

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

5 Answers 5

6
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ 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? $\endgroup$ Jan 11, 2010 at 0:48
  • $\begingroup$ If this graph property was fruitless: How could this be explained, compared to the "unreasonable" fruitfulness of trees? $\endgroup$ Jan 11, 2010 at 0:52
  • 7
    $\begingroup$ Nice pun! Was it intentional? $\endgroup$ Jan 11, 2010 at 1:56
  • $\begingroup$ 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? $\endgroup$ Jan 11, 2010 at 2:21
  • $\begingroup$ @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"? $\endgroup$ Oct 29, 2012 at 18:17
5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ +1, even if this is not really a name but just another characterization. (At least it's something to google for.) $\endgroup$ Jan 25, 2010 at 7:27
3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks. Please see my comments to David's answer. They apply also to yours. $\endgroup$ Jan 11, 2010 at 1:07
  • $\begingroup$ How can vertices of G-v be adjacent to v? $\endgroup$ Jan 11, 2010 at 1:10
  • $\begingroup$ Sorry, I meant adjacent in the original graph. $\endgroup$ Jan 11, 2010 at 1:16
  • $\begingroup$ 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?) $\endgroup$ Jan 11, 2010 at 1:24
0
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

2-connected or biconnected

$\endgroup$
3
  • $\begingroup$ of course, this works only for connected graphs. $\endgroup$ Jan 11, 2010 at 0:32
  • $\begingroup$ A figure-eight graph has every vertex in a cycle but is not biconnected. $\endgroup$ Jan 11, 2010 at 0:36
  • $\begingroup$ 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. $\endgroup$ Jan 11, 2010 at 0:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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