[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
TOPICS
Search

Graph Cycle

A cycle of a graph G, also called a circuit if the first vertex is not specified, is a subset of the edge set of G 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 g 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.

Any cycle of a graph can be expressed as a sum modulo 2 over a fundamental cycle set of the graph (Gould 1959, Paton 1969).

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 k-walks in a graph with adjacency matrix A is given by Tr(A^k), where Tr(A) denotes the matrix trace. In order to compute the number c_k of k-cycles, all closed k-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 k 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 k-cycles c_k is related to the matrix of path counts P_k by

c_k=1/(2k)Tr(P_(k-1)A),
(1)

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

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

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

6c_3=Tr(A^3)
(2)
8c_4=Tr(A^4)-2m-2sum_(i!=j)a_(ij)^((2))
(3)
=sum_(i)a_(ii)^((4))+sum_(i)a_(ii)^((2))-2sum_(i)sum_(j)a_(ij)^((2))
(4)
=Tr(A^4)+Tr(A^2)-2Tr(diag(A^2)^2)
(5)
=Tr(A^4)-2m-2sum_(i)d_i(d_i-1)
(6)
=Tr(A^4)+Tr(A^2)-2sum_(i)d_i^2
(7)
10c_5=Tr(A^5)-5Tr(A^3)-5sum_(i=1)(sum_(j)a_(ij)-2)a_(ii)^((3))
(8)

(with c_4 variants from Perepechko and Voropaev), where m is the number of edges of the graph, a_(ij)^((k)) denotes the i,j element of A^k, diag(A) is the matrix formed from the diagonal elements of A, and d_i=a_(ii)^((2)) is the ith vertex degree. Alon et al. (1997) extended these results up to k=7, although with explicit formulas given only up to k=5. Exact formulas for c_6 and c_7 are given by

12c_6=sum_(i)a_(ii)^((6))-3sum_(n=1)^n(a_(ii)^((3)))^2+9sum_(i)sum_(j)(a_(ij)^((2)))^2a_(ij)-6sum_(i)a_(ii)^((4))d_i+6sum_(i)a_(ii)^((4))-4sum_(i)a_(ii)^((3))+4sum_(i)d_i^3+3sum_(i)sum_(j)a_(ij)^((3))-12sum_(i)d_i^2+4sum_(i)d_i 14c_7=Tr(A^7)-7sum_(i)a_(ii)^((4))a_(ii)^((3))+7sum_(i)sum_(j)(a_(ij)^((2)))^3a_(ij)-7sum_(i)a_(ii)^((5))d_i+21sum_(i)sum_(j)a_(ij)^((3))a_(ij)^((2))a_(ij)+7Tr(A^5)-28sum_(i)sum_(j)(a_(ij)^((2)))^2a_(ij)+7sum_(i)sum_(j)a_(ij)^((2))a_(ij)d_id_j+14sum_(i)a_(ii)^((3))d_i^2+7sum_(i)sum_(j)a_(ii)^((3))a_(ij)^((2))-77sum_(i)a_(ii)^((3))d_i+56Tr(A^3),
(9)

where d_i=a_(ii)^((2)) is the ith 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 n-2, making it computationally expensive. A simplified and improved version of the Khomenko and Golovko formula is given by

c_k=1/(2k)sum_(i=2)^k(-1)^(k-i)(n-i; n-k)sum_(|S|=n-i)Tr(A_S^k)
(10)

for k=3, 4, ..., n, where A_S^k is the kth matrix power of the submatrix of the adjacency matrix A with the subset S of rows and columns deleted (Perepechko and Voropaev). The case k=n therefore gives the number of Hamiltonian cycles.

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

c_k=((-1)^k)/(2k)sum_(H≺_(conn)G)(|N(H)|; k-|H|)(-1)^(|H|)Tr(A_H^k),
(11)

where the sum is over connected induced subgraphs H of G, N(H) denotes the number of neighbors of H in G (namely vertices v of G which are not in H and such that there exists at least one edge from v to a vertex of H), Tr(A) denotes the matrix trace, and A_H^k is the kth matrix power of the adjacency matrix of the graph H.

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

mu<=nu<=2^mu-1
(12)

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

mu(G)=nu(G)
(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 nu=2^mu-1: the complete graphs K_3 and K_4, the complete bipartite graph K_(3,3), and K_4-e (Volkmann 1996).

The total number of undirected cycles also satisfies

nu>=n(1/2delta-1)+1
(14)

and

nu>=1/2delta(delta-1),
(15)

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

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

graphOEISsequence
Andrásfai graphA2346020, 1, 29, 1014, 72273, 9842527, ...
antiprism graphA077263X, X, 63, 179, 523, 1619, 5239, 17379, ...
bishop graphA234636X, 0, 3, 106, 17367, 24601058, 638520866656, ...
(n,n)-black bishop graphA234603X, X, X, 53, 12424, 12300529, ...
cocktail party graph K_(n×2)A1679870, 1, 63, 2766, 194650, 21086055, 3257119761, ...
complete bipartite graph K_(n,n)A0709680, 1, 15, 204, 3940, 113865, 4662231, ...
complete tripartite graph K_(n,n,n)A2346161, 63, 6705, 1960804, 1271288295, 1541975757831, ...
complete graph K_nA0028071, 7, 37, 197, 1172, 8018, ...
2n-crossed prism graphA23461728, 107, 380, 1345, 4878, 18219, ...
crown graphA2346181, 28, 586, 16676, 674171, 36729512, ...
cube-connected cycle graphA000000X, X, 2664, ...
cycle graph C_nA0000121, 1, 1, 1, 1, 1, 1, 1, ...
folded cube graphA2346190, 0, 7, 204, 322248, ...
grid graph P_n square P_nA140517X, 1, 13, 213, 9349, 122236, 487150371, ...
grid graph P_n square P_n square P_nA234620X, 28, 3426491, ...
halved cube graphA2346210, 0, 7, 2766, 4678134804, ...
Hanoi graphA0000001, 11, 1761, ...
hypercube graph Q_nA0854080, 1, 28, 14704, 51109385408, ...
(n,n)-king graphA234622X, 7, 348, 136597, 545217435, 21964731190911, ...
(n,n)-knight graphA234623X, 0, 1, 222, 128769, 959427728, ...
n-ladder graphA0002170, 1, 3, 6, 10, 15, 21, 28, 36, 45, ...
Möbius ladder M_nA020873X, X, 15, 29, 53, 95, 171, 313, 585, ...
Mycielski graphA2346250, 0, 1, 337, 445228418, ...
odd graphA3015580, 1, 57, 872137842, ...
permutation star graphA0000000, 0, 1, 5442, ...
prism graph Y_nA07726514, 28, 52, 94, 170, ...
(n,n)-queen graphA2346260, 7, 8215, 2080941496, 269529670654115055, ...
rook graph K_n square K_nA2346240, 1, 312, 3228524, 6198979538330, ...
Sierpiński gasket graphA2346341, 11, 1033, ...
sun graphA234627X, X, 11, 44, 198, 1036, 6346, 45019, 364039, ...
sunlet graph C_n circledot K_1A000000X, X, 1, 1, 1, 1, 1, 1, 1, 1, ...
triangular graphA2346290, 1, 63, 15703, 58520309, ...
web graphA07726514, 28, 52, 94, 170, 312, 584, 1114, ...
wheel graph W_nA0020617, 13, 21, 31, 43, 57, ...
(n,n)-white bishop graphA234630X, X, X, 53, 4943, 12300529, ...

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

graphformula
antiprism grapha_n=6a_(n-1)-11a_(n-2)+8a_(n-3)-3a_(n-4)+2a_(n-5)-a_(n-6)
complete bipartite graph K_(n,n)1/2sum_(k=2)^(n)k!(k-1)!(n; k)^2
complete graph K_n1/2sum_(k=3)^(n)(k-1)!(n; k)=1/4n[2_3F_1(1,1,1-n;2;-1)-n-1]
cycle graph C_n1
ladder graph(n; 2)
Möbius ladder1+2^n+n(n-1)
prism graph Y_n2^n+n(n-1)
sunlet graph C_n circledot K_11
web graph f2^n+n(n-1)
wheel graph W_n2(n-1)

See also

Acyclic Digraph, Chordless Cycle, Circuit, Cycle Chord, Cycle Graph, Cycle Polynomial, Cyclic Graph, Eulerian Cycle, Eulerian Graph, Eulerian Path, Forest, Fundamental Cycle, Girth, Graph Circumference, Graph Path, Hamiltonian Cycle, Hamiltonian Graph, k-Cyclic Graph, Markström Graph, Square-Free Graph, Trail, Triangle-Free Graph, Unicyclic Graph, Walk Explore this topic in the MathWorld classroom

Explore with Wolfram|Alpha

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. "C_k-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.Gould, R. "The Application of Graph Theory to the Synthesis of Contact Networks." Proc. International Symp. on the Theory of Switching, Pt. I, Apr. 2-5, 1957. In The Annals of the Computation Laboratory of Harvard University, Annals No. 29. Cambridge, MA: Harvard University Press, pp. 244-292, 1959.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.Paton, K. "An Algorithm for Finding Fundamental Cycles of a Graph." Comm. ACM 12, 514-518, 1969.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.

Referenced on Wolfram|Alpha

Graph Cycle

Cite this as:

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

Subject classifications