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

graph classOEISKf(G_1), Kf(G_2), ...
Andrásfai graphA000000/A0000001, 10, 134/7, 3080/109, 263599/7059, 5244806/113017, ...
antiprism graphA000000/A000000X, X, 13/2, 290/21, 551/22, 41, ...
Apollonian networkA000000/A0000003, 834/85, 30154/475, 23555722/44125, 1259601793/263125, ...
cocktail party graph K_(n×2)A000000/A000000infty, 5, 13/2, 25/3, 41/4, 61/5, 85/6, 113/7, 145/8, 181/9, ...
complete bipartite graph K_(n,n)A0000001, 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)A0000002, 13/2, 11, 31/2, 20, 49/2, ...
crossed prism graphA000000X, 58/3, 53, 332/3, 595/3, 322, 1463/3, 2104/3, 969, 3890/3, ...
crown graphA000000/A000000X, X, 35/2, 58/3, 271/12, 131/5, 899/30, 710/21, ...
cube-connected cycle graphA000000/A000000X, X, 346, 6442544/2415, 33760334655251468654052195628373/1958536428315956487415847430, ...
cycle graph C_nA138190/A138191X, X, 2, 5, 10, 35/2, 28, 42, ...
folded cube graphA000000/A000000X, 1, 3, 13, 50, 548/3, 1960/3, 6968/3, 8272, ...
gear graphA000000/A000000X, X, 18, 69/2, 1085/19, 257/3, 8526/71, 6733/42, 10935/53, 53945/209, ...
grid graph P_n square P_nA000000/A0000000, 5, 69/2, 884/7, 11155/33, 2520, 5488, 10752, ...
grid graph P_n square P_n square P_nA000000/A0000000, 58/3, 16959/70, 489296/357, 119593165825/23110593, 136080, ...
halved cube graphA290365/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_nA000000/A000000X, X, 9, 134/7, 1135/33, 725/13, 10367/123, 11732/97, 2835/17, ...
Mycielski graphA000000/A0000000, 1, 10, 4545/139, 8808777389/93842615, ...
odd graph O_nA000000/A0000000, 2, 33, 373, 4000, 264001/6, ...
pan graphA000000/A000000X, X, 19/3, 23/2, 19, 88/3, 43, ...
path graph P_nA0000000, 1, 4, 10, 20, 35, 56, 84, 120, 165, ...
permutation star graph PS_nA000000/A0000000, 1, 35/2, 1314/5, 26520, 963598/7, ...
prism graph Y_nA000000/A000000X, X, 47/5, 58/3, 655/19, 279/5, ...
rook graph K_n square K_nA000000/A000000X, 5, 18, 42, 80, 135, 210, 308, 432, ...
star graph S_nA0002900, 1, 4, 9, 16, 25, 36, 49, 64, 81, ...
sun graphA000000/A000000X, X, 65/6, 302/15, 75, 114, 161, 216, 279, 350, 429, ...
sunlet graph C_n circledot K_1A000000/A000000X, X, 23, 48, 105, 174, 259, 376, 513, 690, 891, ...
tetrahedral graphA000000/A000000X, X, X, X, X, 43, 207/2, 1945/9, 4901/12, 2149/3, ...
triangular graphA000000/A000000X, 0, 2, 13/2, 57/4, 26, 85/2, 129/2, 371/4, 128, ...
web graphA000000/A000000X, X, 222/5, 173/2, 2780/19, 4521/20, 23282/71, 3179/7, 160848/265, ...
wheel graph W_nA000000/A000000X, 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). Here, H_n is a harmonic number and Phi(z,s,a) is the Lerch transcendent.

graphKf(G_n)
cocktail party graph K_(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 graph1/3(3n^3-10n+7)
crown graph(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_n-2^(n-1)H_n-4^nR[Phi(z,1,n+1)]
pan graph1/(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 graph1/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, A290343, A290344, A290347, A290348, A290365, 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 Web Resource. https://mathworld.wolfram.com/KirchhoffIndex.html

Subject classifications