k-Cyclic Graph

Graphs corresponding to closed walks of length  are known as -cyclic graphs, or -graphs for short. -graphs are connected by definition. The numbers of -graphs for , 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  for some value of . For example, every connected graph on six or fewer nodes with the exception of the complete graph  is  for some .

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

REFERENCES

Alon, N.; Yuster, R.; and Zwick, U. "Finding and Counting Given Length Cycles." Algorithmica 17, 209-223, 1997.

FlowProblem. "-Graphs." http://flowproblem.ru/cycles/explicit-formulae/ck-graphs.