most recent 30 from http://mathoverflow.net 2013-05-24T16:34:00Z http://mathoverflow.net/feeds/question/11384 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/11384/whats-the-name-of-graphs-with-each-vertex-contained-in-a-cycle Hans Stricker 2010-01-11T00:29:01Z 2010-02-18T00:26:09Z

<p>A tree is a graph with <strong>no</strong> vertex contained in a cycle.</p> <p>A non-tree is a graph with <strong>some</strong> vertex contained in a cyle.</p> <blockquote> <p>What's the name of graphs with <strong>each</strong> vertex contained in a cycle?</p> </blockquote>

http://mathoverflow.net/questions/11384/whats-the-name-of-graphs-with-each-vertex-contained-in-a-cycle/11386#11386 Klingonesque 2010-01-11T00:31:54Z 2010-01-11T00:31:54Z

<p>2-connected or biconnected</p>

http://mathoverflow.net/questions/11384/whats-the-name-of-graphs-with-each-vertex-contained-in-a-cycle/11387#11387 David Eppstein 2010-01-11T00:38:29Z 2010-01-11T00:38:29Z

<p>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.</p>

http://mathoverflow.net/questions/11384/whats-the-name-of-graphs-with-each-vertex-contained-in-a-cycle/11389#11389 Harrison Brown 2010-01-11T01:04:32Z 2010-01-11T01:45:44Z

<p>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:</p> <p>$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.</p> <p>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.</p> <p>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.</p> <p>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.)</p> <p>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.</p>

http://mathoverflow.net/questions/11384/whats-the-name-of-graphs-with-each-vertex-contained-in-a-cycle/12901#12901 Douglas S. Stones 2010-01-25T04:40:25Z 2010-01-25T04:40:25Z

<p>These are the graphs that admit "vertex cycle covers". <a href="http://en.wikipedia.org/wiki/Vertex%5Fcycle%5Fcover" rel="nofollow">http://en.wikipedia.org/wiki/Vertex_cycle_cover</a></p>

http://mathoverflow.net/questions/11384/whats-the-name-of-graphs-with-each-vertex-contained-in-a-cycle/15646#15646 Tony Huynh 2010-02-17T23:48:33Z 2010-02-18T00:26:09Z

<p>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:</p> <p>Every vertex of $G$ is contained in a block of $G$ which is not a $K_2$.</p> <p>Of course, this is the same answer as Harrison's, but it gives a more global view. Also, necessity and sufficiency are trivial. </p>