TOPICS
Search

Unicyclic Graph


A unicyclic graph is a connected graph containing exactly one cycle (Harary 1994, p. 41). A connected unicyclic graph is therefore a pseudotree that is not a tree.

Truszczyński (1984) conjectured that all unicyclic graphs except the cycle graph C_n with n=1 or 2 (mod 4) are graceful (Gallian 2018).

UnicyclicGraphs

The numbers of unicyclic graphs on n=1, 2, ... vertices are 0, 0, 1, 3, 9, 25, 68, 185, ... (OEIS A236570), the first few of which are illustrated above.

UnicyclicConnectedGraphs

The corresponding numbers of connected unicyclic graphs are 0, 0, 1, 2, 5, 13, 33, 89, ... (OEIS A001429), the first few of which are illustrated above.

Examples of unicyclic classes of graphs include (n,3)-caveman graphs, cycle graphs C_n, pan graphs, sunlet graphs C_n circledot K_1, and tadpole graphs.


See also

Acyclic Graph, Cyclic Graph, Graph Cycle, Pseudotree, Tree

Explore with Wolfram|Alpha

References

Gallian, J. "Dynamic Survey of Graph Labeling." Elec. J. Combin. DS6. Dec. 21, 2018. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Sloane, N. J. A. Sequences A001429/M1438 and A236570 in "The On-Line Encyclopedia of Integer Sequences."Truszczyński, M. "Graceful Unicyclic Graphs." Demonstatio Math. 17, 377-387, 1984.

Referenced on Wolfram|Alpha

Unicyclic Graph

Cite this as:

Weisstein, Eric W. "Unicyclic Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/UnicyclicGraph.html

Subject classifications