Graph Cycle

A cycle of a graph , also called a circuit if the first vertex is not specified, is a subset of the edge set of  that forms a path such that the first node of the path corresponds to the last. A maximal set of edge-disjoint cycles of a given graph  can be obtained using ExtractCycles[g] in the Wolfram Language package Combinatorica` .

A cycle that uses each graph vertex of a graph exactly once is called a Hamiltonian cycle.

A graph containing no cycles of length three is called a triangle-free graph, and a graph containing no cycles of length four is called a square-free graph.

A graph containing no cycles of any length is known as an acyclic graph, whereas a graph containing at least one cycle is called a cyclic graph. A graph possessing exactly one (undirected, simple) cycle is called a unicyclic graph. A connected acyclic graph is known as a tree, and a possibly disconnected acyclic graph is known as a forest.

The length of the shortest graph cycle (if any) in a given graph is known as the girth, and the length of a longest cycle is known as the graph circumference.

The minimum number of swaps between vertices in a random circular embedding of a cycle to put in its standard configuration is considered by Björner and Wachs (1982) and (Stanley 1999).

An acyclic graph is bipartite, and a cyclic graph is bipartite iff all its cycles are of even length (Skiena 1990, p. 213).

The number of (undirected) closed -walks in a graph with adjacency matrix  is given by , where  denotes the matrix trace. In order to compute the number  of -cycles, all closed -walks that are not cycles must be subtracted. One would think that by analogy with the matching-generating polynomial, independence polynomial, etc., a cycle polynomial whose coefficients are the numbers of cycles of length  would be defined. While no such polynomial seems not to have been defined in the literature (instead, "cycle polynomials" commonly instead refers to a polynomial corresponding to cycle indices of permutation groups), they are defined in this work.

The number of -cycles  is related to the matrix of path counts  by

(1)

where  denotes the matrix trace and  is the adjacency matrix (Perepechko and Voropaev).

Graphs corresponding to closed walks of length  are known as k-cyclic graphs, or "-graphs" for short. 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).

Harary and Manvel (1972) gave the following closed forms for small :

			(2)
			(3)
			(4)
			(5)
			(6)
			(7)
			(8)

(with  variants from Perepechko and Voropaev), where  is the number of edges of the graph,  denotes the  element of ,  is the matrix formed from the diagonal elements of , and  is the th vertex degree. Alon et al. (1997) extended these results up to , although with explicit formulas given only up to . Exact formulas for  and  are given by

(9)

where  is the th vertex degree (Perepechko and Voropaev; S. Perepechko, pers. comm., Jan. 4, 2014).

Khomenko and Golovko (1972) gave a formula giving the number of cycles of any length, but its computation requires computing and performing matrix operations involving all subsets up to size , making it computationally expensive. A simplified and improved version of the Khomenko and Golovko formula is given by

(10)

for , 4, ..., , where  is the th matrix power of the submatrix of the adjacency matrix  with the subset  of rows and columns deleted (Perepechko and Voropaev). The case  therefore gives the number of Hamiltonian cycles.

Giscard et al. (2016) gave the formula for the number of undirected -cycles in a graph  as

(11)

where the sum is over connected induced subgraphs  of ,  denotes the number of neighbors of  in  (namely vertices  of  which are not in  and such that there exists at least one edge from  to a vertex of ),  denotes the matrix trace, and  is the th matrix power of the adjacency matrix of the graph .

Let  denote the total number of undirected cycles in a graph and  the circuit rank. Then

(12)

(Kirchhoff 1847, Ahrens 1897, König 1936, Volkmann 1996). The total numbers of undirected cycles for all simple graphs of orders , 2, ... are 0, 0, 1, 13, 143, 1994, 39688, ... (OEIS A234601).

(13)

iff any two cycles have no edge in common (Volkmann 1996). Among connected graphs, the equality therefore holds for (and only for) cactus graphs. Mateti and Deo (1976) proved that there are "essentially" only four graphs with : the complete graphs  and , the complete bipartite graph , and  (Volkmann 1996).

The total number of undirected cycles also satisfies

(14)

and

(15)

where  is the number of vertices and  is the minimum vertex degree (Volkmann 1996).

The following table gives the number of undirected graph cycles for various classes of graphs.

graph	OEIS	sequence
Andrásfai graph	A234602	0, 1, 29, 1014, 72273, 9842527, ...
antiprism graph	A077263	X, X, 63, 179, 523, 1619, 5239, 17379, ...
bishop graph	A234636	X, 0, 3, 106, 17367, 24601058, 638520866656, ...
-black bishop graph	A234603	X, X, X, 53, 12424, 12300529, ...
cocktail party graph	A167987	0, 1, 63, 2766, 194650, 21086055, 3257119761, ...
complete bipartite graph	A070968	0, 1, 15, 204, 3940, 113865, 4662231, ...
complete tripartite graph	A234616	1, 63, 6705, 1960804, 1271288295, 1541975757831, ...
complete graph	A002807	1, 7, 37, 197, 1172, 8018, ...
-crossed prism graph	A234617	28, 107, 380, 1345, 4878, 18219, ...
crown graph	A234618	1, 28, 586, 16676, 674171, 36729512, ...
cube-connected cycle	A000000	X, X, 2664, ...
cycle graph	A000012	1, 1, 1, 1, 1, 1, 1, 1, ...
folded cube graph	A234619	0, 0, 7, 204, 322248, ...
grid graph	A140517	X, 1, 13, 213, 9349, 122236, 487150371, ...
grid graph	A234620	X, 28, 3426491, ...
halved cube graph	A234621	0, 0, 7, 2766, 4678134804, ...
Hanoi graph	A000000	1, 11, 1761, ...
hypercube graph	A085408	0, 1, 28, 14704, 51109385408, ...
-king graph	A234622	X, 7, 348, 136597, 545217435, 21964731190911, ...
-knight graph	A234623	X, 0, 1, 222, 128769, 959427728, ...
-ladder graph	A000217	0, 1, 3, 6, 10, 15, 21, 28, 36, 45, ...
Möbius ladder	A020873	X, X, 15, 29, 53, 95, 171, 313, 585, ...
Mycielski graph	A234625	0, 0, 1, 337, 445228418, ...
odd graph	A301558	0, 1, 57, 872137842, ...
permutation star graph	A000000	0, 0, 1, 5442, ...
prism graph	A077265	14, 28, 52, 94, 170, ...
-queen graph	A234626	0, 7, 8215, 2080941496, 269529670654115055, ...
rook graph	A234624	0, 1, 312, 3228524, 6198979538330, ...
Sierpiński sieve graph	A234634	1, 11, 1033, ...
sun graph	A234627	X, X, 11, 44, 198, 1036, 6346, 45019, 364039, ...
sunlet graph	A000000	X, X, 1, 1, 1, 1, 1, 1, 1, 1, ...
triangular graph	A234629	0, 1, 63, 15703, 58520309, ...
web graph	A077265	14, 28, 52, 94, 170, 312, 584, 1114, ...
wheel graph	A002061	7, 13, 21, 31, 43, 57, ...
-white bishop graph	A234630	X, X, X, 53, 4943, 12300529, ...

Closed forms for some of these classes of graphs are summarized in the following table.

graph	formula
antiprism graph
complete bipartite graph
complete graph
cycle graph	1
ladder graph
Möbius ladder
prism graph
sunlet graph	1
web graph f
wheel graph

---

REFERENCES

Ahrens, W. "Über das Gleichungssystem einer Kirchhoffschen galvanischen Stromverzweigung." Math. Ann. 49, 311-324, 1897.

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

Björner, A. and Wachs, M. "Bruhat Order of Coxeter Groups and Shellability." Adv. Math. 43, 87-100, 1982.

FlowProblem. "-Graphs." http://flowproblem.ru/cycles/explicit-formulae/ck-graphs.Giscard, P.-L.; Kriege, N.; and Wilson, R. C. "A General Purpose Algorithm for Counting Simple Cycles and Simple Paths of Any Length." 16 Dec 2016. 

https://arxiv.org/pdf/1612.05531.pdf.Harary, F. and Manvel, B. "On the Number of Cycles in a Graph." Mat. Časopis Sloven. Akad. Vied 21, 55-63, 1971.

Karavaev, A. M. "FlowProblem: Statistics of Simple Cycles." http://flowproblem.ru/paths/statistics-of-simple-cycles.Khomenko, N. P. and Golovko, L. D. "Identifying Certain Types of Parts of a Graph and Computing Their Number." Ukr. Math. J. 24, 313-321, 1972.

Kirchhoff, G. "Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird." Ann. d. Phys. Chem. 72, 497-508, 1847.

König, D. Theorie der endlichen und unendlichen Graphen. Leipzig, Germany: Akademische Verlagsgesellschaft, 1936.

Mateti, P. and Deo, N. "On Algorithms for Enumerating All Circuits of a Graph." SIAM J. Comput. 5, 90-99, 1976.

Perepechko, S. N. and Voropaev, A. N. "The Number of Fixed Length Cycles in an Undirected Graph. Explicit Formulae in Case of Small Lengths."Skiena, S. "Cycles in Graphs." §5.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 188-202, 1990.

Sloane, N. J. A. Sequences A000012/M0003, A002061/M2638, A002807/M4420, A077263, A077265, A081809, and A234601 in "The On-Line Encyclopedia of Integer Sequences."Stanley, R. P. Enumerative Combinatorics, Vol. 1. Cambridge, England: Cambridge University Press, 1999.

Volkmann, L. "Estimations for the Number of Cycles in a Graph." Per. Math. Hungar. 33, 153-161, 1996.

West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 5 and 20, 2000.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength