TOPICS
Search

Kirchhoff Index

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The Kirchhoff index Kf, also simply called the resistance and denoted R (Lukovits et al. 1999), of a finite connected graph G on n nodes is defined by

Kf=1/2sum_(i=1)^nsum_(j=1)^n(Omega)_(ij),

where (Omega)_(ij) is the resistance distance matrix.

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 are implemented in the Wolfram Language as GraphData[g, "KirchhoffIndex"].

The following table summarizes values of the Kirchhoff index for various special classes of graphs. The index of each value list in the table starts at 1. An X indicates that the family in that row is not defined for the corresponding parameter value or has no value in the domain of connected graphs. In the tables, crossed prism graphs are parametrized by a cycle size of 2n. The sun graph row uses the complete n-sun convention.

graph classOEISKf(G_1), Kf(G_2), ...
Andrásfai graph1, 10, 134/7, 3080/109, 263599/7059, 5244806/113017, ...
antiprism graphX, X, 13/2, 290/21, 551/22, 41, ...
Apollonian network3, 834/85, 30154/475, 23555722/44125, 1259601793/263125, ...
cocktail party graph K_(n×2)infty, 5, 13/2, 25/3, 41/4, 61/5, 85/6, 113/7, 145/8, 181/9, ...
complete bipartite graph K_(n,n)1, 5, 9, 13, 17, 21, 25, 29, 33, 37, ...
complete graph K_nA0014770, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
complete tripartite graph K_(n,n,n)2, 13/2, 11, 31/2, 20, 49/2, ...
crossed prism graph with cycle size 2nX, 58/3, 53, 332/3, 595/3, 322, 1463/3, 2104/3, 969, 3890/3, ...
crown graphX, X, 35/2, 58/3, 271/12, 131/5, 899/30, 710/21, ...
cube-connected cycle graphX, X, 346, 6442544/2415, 33760334655251468654052195628373/1958536428315956487415847430, ...
cycle graph C_nA138190/A138191X, X, 2, 5, 10, 35/2, 28, 42, ...
folded cube graphX, 1, 3, 13, 50, 548/3, 1960/3, 6968/3, 8272, ...
gear graphX, X, 18, 69/2, 1085/19, 257/3, 8526/71, 6733/42, 10935/53, 53945/209, ...
grid graph P_n square P_n0, 5, 69/2, 884/7, 11155/33, 535131/715, 47274465/32422, 111014696336/42859159, ...
grid graph P_n square P_n square P_n0, 58/3, 16959/70, 489296/357, 119593165825/23110593, 3959047278723/259814555, ...
halved cube graphA290165/A2903660, 1, 3, 25/3, 70/3, 3014/45, 2968/15, 63148/105, 197072/105, ...
hypercube graph Q_nA290343/A2903441, 5, 58/3, 206/3, 3548/15, ...
Möbius ladder M_nX, X, 9, 134/7, 1135/33, 725/13, 10367/123, 11732/97, 2835/17, ...
Mycielski graph0, 1, 10, 4545/139, 8808777389/93842615, ...
odd graph O_n0, 2, 33, 373, 4000, 264001/6, ...
pan graphX, X, 19/3, 23/2, 19, 88/3, 43, ...
path graph P_n0, 1, 4, 10, 20, 35, 56, 84, 120, 165, ...
permutation star graph PS_n0, 1, 35/2, 1314/5, 26520, 963598/7, ...
prism graph Y_nX, X, 47/5, 58/3, 655/19, 279/5, ...
rook graph K_n square K_n0, 5, 18, 42, 80, 135, 210, 308, 432, ...
star graph S_nA0002900, 1, 4, 9, 16, 25, 36, 49, 64, 81, ...
sun graphX, X, 65/6, 302/15, 1955/62, 1169/26, 74543/1234, 188044/2415, 3606873/37058, 16594610/139683, 213092209/1497718, ...
sunlet graph C_n circledot K_1X, X, 23, 48, 85, 136, 203, 288, 393, 520, 671, ...
tetrahedral graphX, X, X, X, X, 43, 207/2, 1945/9, 4901/12, 2149/3, ...
triangular graphX, 0, 2, 13/2, 57/4, 26, 85/2, 129/2, 371/4, 128, ...
web graphX, X, 222/5, 173/2, 2780/19, 4521/20, 23282/71, 3179/7, 160848/265, ...
wheel graph W_nX, X, X, 16/3, 95/11, 129/10, ...

Closed forms are summarized in the following table. The cycle graph was considered by Klein et al. (1995) and Babić et al. (2002). The hypercube graph formula uses the binomial coefficient (n; k). For disconnected graphs, the displayed value infty is an extension by convention.

graphKf(G_n)
cocktail party graph K_(n×2) with n>=2(2n^2-2n+1)/(n-1)
complete bipartite graph K_(n,n)4n-3
complete graph K_nn-1
complete tripartite graph K_(n,n,n)1/2(9n-5)
crossed prism graph with cycle size 2n1/3n(3n^2+9n-1)
crown graph with n>=3(4n^3-11n^2+10n-4)/((n-2)(n-1))
cycle graph C_n with n>=31/(12)(n-1)n(n+1)
empty graph K^__n{0 for n=1; infty otherwise
hypercube graph Q_n2^(n-1)sum_(k=1)^(n)1/k(n; k)
pan graph with n>=31/(12)(n^3+2n^2+11n-2)
path graph P_n1/6(n-1)n(n+1)
rook graph K_n square K_n1/2(n-1)n(n+3)
star graph S_n(n-1)^2
triangular graph with n>=21/8(n-2)(n^2+3n-2)

See also

Balaban Index, Graph Distance Matrix, Kirchhoff Sum Index, Resistance Distance, Wiener Index, Wiener Sum Index

Explore with Wolfram|Alpha

References

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.Bonchev, D.; Balaban, A. T.; Liu, X.; and Klein, D. J. "Molecular Cyclicity and Centricity of Polycyclic Graphs. I. Cyclicity Based on Resistance Distances or Reciprocal Distances." Int. J. Quan. Chem. 50, 1-20, 1994.Devillers, J. and Balaban, A. T. (Eds.). Topological Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands: Gordon and Breach, pp. 40-41 and 114, 1999.Klein, D. J.; Lukovits, I.; and Gutman, I. "On the Definition of the Hyper-Wiener Index for Cycle-Containing Structures." J. Chem. Inf. Comput. 35, 50-52, 1995.Lukovits, I.; Nikolić, S.; and Trinajstić, N. "Resistance Distance in Regular Graphs." Int. J. Quan. Chem. 71, 217-225, 1999.Palacios, J. L. "Closed-Form Formulas for Kirchhoff Index." Int. J. Quant. Chem. 81, 135-140, 2001.Sloane, N. J. A. Sequences A000290/M3356, A001477, A138190, A138191, A290165, A290343, A290344, A290347, A290348, and A290366 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Kirchhoff Index

Cite this as:

Weisstein, Eric W. "Kirchhoff Index." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/KirchhoffIndex.html

Subject classifications