The circuit rank ,
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. 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.
name
references
circuit rank
Waller (1976, p. 242), Wilson
(1985, p. 46)
cycle rank
Harary
(1994, p. 39), White (2001, p. 56), Gross and Yellen (2006, pp. 192
and 661)
(first) graph Betti number
White (2001), Gross and Yellen (2006, pp. 192)
cyclomatic number
Listing (1862), Veblen (1916,
pp. 9 and 18)
graph nullity
Chen
(1976, p. 11)
notation
references
Veblen (1916, pp. 9 and 18), Volkmann (1996), Babić et
al. (2002)
Waller (1976, p. 242), Wilson
(1985, p. 46), Tomescu (2022, p. 110)
Gross and Yellen
(2006, pp. 192 and 661), 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).
Precomputed values for many graphs is implemented in the Wolfram Language as GraphData[g,
"CircuitRank"].
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.Chen, W.-K. Applied
Graph Theory: Graphs and Electrical Networks, 2nd rev. ed. Amsterdam, Netherlands:
North-Holland, p. 11, 1976.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.Tomescu, I. "Graphs with Given Cyclomatic Number Extremal
Relatively to Vertex Degree Function Index for Convex Functions." MATCH Commun.
Math. Comput. Chem.87, 109-114, 2022. https://doi.org/10.46793/match.87-1.109T.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.Waller, D. A. "Double Covers of Graphs."
Bull. Austral. Math. Soc.14, 233-248, 1976. https://doi.org/10.1017/S0004972700025053.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, 3rd ed. Harlow, England: Longman, p. 46, 1985.
,
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. 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.
, vertex count 
, and 
connected components,
the circuit rank is given by
iff it is a tree
and has 
iff it is a unicyclic graph.
More generally, a graph is a pseudoforest iff
every connected component has circuit rank
0 or 1, and a connected pseudoforest is a pseudotree.
for circuit rank is unrelated to the 
used for the mutual-visibility
number, the 
of the matching polynomial, and the 
parameter of a strongly
regular graph.
given by
:
the complete graphs 
and 
, the complete bipartite
graph 
,
and 
(Volkmann 1996).
