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?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
7
|
|
|||||
|
|
0
|
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. |
|||
|
|
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.
|
3
|
These are the graphs that admit "vertex cycle covers". http://en.wikipedia.org/wiki/Vertex_cycle_cover |
|||
|
|
3
|
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. |
||||||||||||
|
|
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. |
|||||||||||||||||
|
|
-2
|
2-connected or biconnected |
|||||||||
|
