Circuit Rank

The circuit rank , also denoted  (Volkmann 1996, Babić et al. 2002) or  (White 2001, p. 56) and known as the cycle rank (e.g., White 2001, p. 56), graph Betti number (e.g., White 2001), cyclomatic number, or graph nullity, is the smallest number of graph edges which must be removed from an undirected graph on  graph edges and  nodes such that no graph cycle remains. It is given by

(1)

for a graph with  connected components.

The circuit rank gives the number of independent cycles in the cycle basis of a graph (Harary 1994, pp. 37-40; White 2001, p. 56).

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

(2)

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

(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 : the complete graphs  and , the complete bipartite graph , and  (Volkmann 1996).

Unless otherwise stated, hydrogen atoms are usually ignored in the computation of such indices as organic chemists usually do when they write a benzene ring as a hexagon (Devillers and Balaban 1999, p. 25).

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

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.

Harary, 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.

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

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.