TOPICS
Search

k-Cyclic Graph


k-CyclicGraphs

Graphs corresponding to closed walks of length k are known as k-cyclic graphs, or C_k-graphs for short. C_k-graphs are connected by definition. The numbers of C_k-graphs for k=3, 4, ... are 1, 3, 3, 10, 12, 35, 58, 160, 341, 958, 2444, 7242, 21190, 67217, 217335, ... (OEIS A081809; FlowProblems), the first few of which are illustrated above.

It appears that every connected simple graph on more than one node is C_k for some value of k. For example, every connected graph on six or fewer nodes with the exception of the complete graph K_6 is C_k for some 3<=k<=17.

These graphs are important when counting graph cycles. This is because the number of (undirected) closed k-walks in a graph with adjacency matrix A is given by Tr(A^k), where Tr(A) denotes the matrix trace, but in order to compute the number c_k of k-cycles, all closed k-walks that are not cycles must be subtracted.


See also

Circuit, Cyclic Graph, Graph Cycle, Hamiltonian Walk, Trail, Walk

Explore with Wolfram|Alpha

References

Alon, N.; Yuster, R.; and Zwick, U. "Finding and Counting Given Length Cycles." Algorithmica 17, 209-223, 1997.FlowProblem. "C_k-Graphs." http://flowproblem.ru/cycles/explicit-formulae/ck-graphs.

Cite this as:

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

Subject classifications