TOPICS
Search

Pancyclic Graph


A simple unlabeled graph on n vertices is called pancyclic if it contains cycles of all lengths, 3, 4, ..., n. Since a pancyclic graph must contain a cycle of length n, pancyclic graphs are of necessity Hamiltonian.

PancyclicGraphs

The numbers of pancyclic graphs on n=1, 2, ... vertices are 0, 0, 1, 2, 7, 43, 372, 6132, 176797, 9302828, ... (OEIS A286684), the first few of which are illustrated above.

Classes of graphs which are pancyclic include:

1. antiprism graphs,

2. Chang graphs,

3. dipyramidal graphs,

4. Johnson graphs,

5. Mathon graphs,

6. Paulus graphs,

7. Sierpiński gasket graphs,

8. sun graphs,

9. tetrahedral graphs, and

10. wheel graphs.

Pancyclic graphs that have exactly one cycle of each length are very rare and are known as uniquely pancyclic graphs.


See also

Graph Cycle, Hamiltonian Graph, Uniquely Pancyclic Graph

Explore with Wolfram|Alpha

References

George, J. C.; Khodkar, A.; and Wallis, W. D. Pancyclic and Bipancyclic Graphs. Cham, Switzerland: Springer, 2016.Sloane, N. J. A. Sequence A286684 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Pancyclic Graph

Cite this as:

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

Subject classifications