TOPICS
Search

Circuit Rank


The circuit rank mu, is the smallest number of graph edges which must be removed from an undirected graph on m graph edges and n nodes such that no graph cycle remains. The circuit rank also gives the number of fundamental cycles in a cycle basis of a graph (Harary 1994, pp. 37-40; White 2001, p. 56). The concept was first introduced by Gustav Kirchhoff (Kirchhoff 1847; Veblen 1916, p. 9; Kotiuga 2010, p. 20), and has been referred to by a number of different names and symbols as summarized in the following tables.

namereferences
circuit rank
cycle rankHarary (1994, p. 39), White (2001, p. 56), Gross and Yellen (2006, pp. 192 and 661)
(first) graph Betti numberGross and Yellen (2006, pp. 192), White (2001)
cyclomatic numberListing (1862), Veblen (1916, pp. 9 and 18)
graph nullity
notationreferences
muVeblen (1916, pp. 9 and 18), Volkmann (1996), Babić et al. (2002)
gamma
betaGross and Yellen (2006, pp. 192 and 661), White (2001, p. 56)
mHarary (1994, p. 39)

For a graph with edge count m, vertex count n, and c connected components, the circuit rank is given by

 mu=m-n+c.
(1)

The circuit rank provides an inequality on the total number of undirected graph cycles nu given by

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

(Kirchhoff 1847, Ahrens 1897, König 1936, Volkmann 1996). Furthermore,

 mu(G)=nu(G)
(3)

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).

Precomputed values for many graphs is implemented in the Wolfram Language as GraphData[g, "CircuitRank"].


See also

Balaban Index, Betti Number, Cactus Graph, Connected Component, Edge Count, Graph Cycle, Vertex Count

Explore with Wolfram|Alpha

References

Ahrens, W. "Über das Gleichungssystem einer Kirchhoffschen galvanischen Stromverzweigung." Math. Ann. 49, 311-324, 1897.Babić, D.; Klein, D. J.; Lukovits, I.; Nikolić, S.; and Trinajstić, N. "Resistance-Distance Matrix: A Computational Algorithm and Its Applications." Int. J. Quant. Chem. 90, 166-176, 2002.Devillers, J. and Balaban, A. T. (Eds.). Topological Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands: Gordon and Breach, 1999.Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, 2006.HararyHarary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.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.Kotiuga, P. R. A Celebration of the Mathematical Legacy of Raoul Bott. Providence, RI: Amer. Math. Soc., 2010.Listing, J. B. Census raumliche Komplexe. Göttingen, Germany: 1862.Mateti, P. and Deo, N. "On Algorithms for Enumerating All Circuits of a Graph." SIAM J. Comput. 5, 90-99, 1976.Veblen, O. Analysis Situs. New York: Amer. Math. Soc., 1916.Volkmann, L. "Estimations for the Number of Cycles in a Graph." Per. Math. Hungar. 33, 153-161, 1996.White, A. T. "Imbedding Problems in Graph Theory." Ch. 6 in Graphs of Groups on Surfaces: Interactions and Models (Ed. A. T. White). Amsterdam, Netherlands: Elsevier, pp. 49-72, 2001.Wilson, R. J. Introduction to Graph Theory. Edinburgh: Oliver and Boyd, p. 46, 1971.

Referenced on Wolfram|Alpha

Circuit Rank

Cite this as:

Weisstein, Eric W. "Circuit Rank." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CircuitRank.html

Subject classifications