TOPICS
Search

Harary Index

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The Harary index of a graph G on n vertices was defined by Plavšić et al. (1993) as

H(G)=1/2sum_(i=1)^nsum_(j=1)^n(RD)_(ij),
(1)

where

(RD)_(ij)={D_(ij)^(-1) if i!=j; 0 if i=j
(2)

is the reciprocal of the graph distance matrix D (Plavšić et al. 1993; Devillers and Balaban 1999, p. 80).

Some care is needed, since while some authors include the leading factor of 1/2 (e.g., Plavšić et al. 1993, Mercader et al. 2001), others omit it (e.g., Devillers and Balaban 1999, pp. 111 and 202).

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

The following table summarizes values of the Harary 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. All values use the leading factor of 1/2. For vertices in different connected components, the graph distance is taken to be infinite and its reciprocal is 0. The rook graph complement at n=2 consists of two disjoint edges and has index 2. Its cited sequence agrees with the index for n>=3. The closed form for the cocktail party graph applies for n>=2 and has the exceptional value 0 at n=1. The crown graph closed form applies for n>=3, with values 0 and 2 at n=1 and 2. The sequence cited for the white bishop graph starts at n=2.

graph classOEISH(G_1), H(G_2), ...
Andrásfai graph1, 15/2, 20, 77/2, 63, 187/2, 130, 345/2, 221, ...
antiprism graphX, X, 27/2, 22, 95/3, 42, 637/12, 194/3, 384/5, ...
Apollonian network6, 18, 80, 470, 3248, 122106/5, 958184/5, 7694739/5, ...
bishop graph B_(n,n)A2961970, 2, 13, 42, 102, 208, 379, 636, 1004, 1510, ...
black bishop graph BB_(n,n)A2961980, 1, 8, 21, 55, 104, 197, 318, 514, 755, ...
cocktail party graph K_(n×2)0, 5, 27/2, 26, 85/2, 63, 175/2, 116, 297/2, 185, ...
complete bipartite graph K_(n,n)A0003261, 5, 12, 22, 35, 51, 70, 92, ...
complete graph K_nA0002170, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, ...
complete tripartite graph K_(n,n,n)3, 27/2, 63/2, 57, 90, 261/2, ...
2n-crossed prism graphX, 58/3, 39, 184/3, 257/3, 558/5, 2083/15, 17564/105, ...
crown graph0, 2, 10, 58/3, 95/3, 47, 196/3, 260/3, 111, 415/3, ...
cube-connected cycle graphX, X, 556/5, 57376/105, 162634/63, 34149904/3003, ...
cycle graph C_nA160046/A160047X, X, 3, 5, 15/2, 10, 77/6, 47/3, 75/4, 131/6, ...
Fibonacci cube graph1, 5/2, 22/3, 71/4, 216/5, 1219/12, 25033/105, ...
folded cube graphX, 1, 6, 22, 80, 808/3, 2800/3, 9488/3, 11072, ...
gear graphX, X, 29/2, 133/6, 125/4, 167/4, 161/3, 67, 327/4, ...
grid graph P_n square P_nA296191/A2961920, 5, 133/6, 293/5, 3399/28, 137111/630, 140351/396, ...
grid graph P_n square P_n square P_n0, 58/3, 2402/15, 30617/45, 7168769/3465, ...
halved cube graphA290347/A2903480, 1, 6, 26, 100, 1096/3, 3920/3, 13936/3, 16544, ...
Hanoi graph3, 22, 4276/35, 1835837/3003, 175359949924361/60168147039, ...
helm graphX, X, 29/2, 133/6, 125/4, 167/4, 161/3, 67, 327/4, ...
hypercube graph Q_nA290343/A2903441, 5, 58/3, 206/3, 3548/15, 12136/15, 291824/105, ...
Keller graph K_nA2961890, 80, 1552, 27264, 460544, 7634944, ...
king graph Ki_(n,n)A1449450, 6, 28, 76, 160, 290, 476, 728, 1056, 1470, ...
knight graph Kn_(n,n)0, 0, 47/3, 309/5, 150, 1769/6, 7724/15, 24733/30, ...
Menger sponge graph1147/15, 207460203161/19684665, ...
Möbius ladderX, X, 12, 20, 85/3, 38, 287/6, 176/3, 348/5, 244/3, ...
Mycielski graphA2961930, 1, 15/2, 75/2, 162, 1317/2, 2610, 20505/2, 40212, ...
odd graph O_n0, 3, 30, 280, 2730, 57057/2, 635635/2, ...
pan graphX, X, 5, 22/3, 61/6, 155/12, 16, 571/30, 1339/60, ...
path graph P_nA027612/A0276110, 1, 5/2, 13/3, 77/12, 87/10, 223/20, 481/35, ...
permutation star graph PS_nA296190/A2960570, 1, 10, 123, 2202, 59040, 2287680, 121394000, ...
prism graph Y_nX, X, 12, 58/3, 85/3, 75/2, 287/6, 874/15, ...
queen graph Q_(n,n)A2961960, 6, 32, 98, 230, 460, 826, 1372, 2148, 3210, ...
rook complement graph K_n square K_n^_A0923640, 2, 27, 96, 250, 540, 1029, 1792, 2916, 4500, ...
rook graph K_n square K_nA0857400, 5, 27, 84, 200, 405, 735, 1232, 1944, 2925, ...
Sierpiński carpet graph47/3, 23255059/51480, ...
Sierpiński gasket graph3, 12, 227/4, 5553/20, 161390213/120120, ...
Sierpiński tetrahedron graph6, 69/2, 1055/4, 599803/280, 279423163/16016, ...
star graph S_nA160050/A1306580, 1, 5/2, 9/2, 7, 10, 27/2, 35/2, 22, 27, ...
sun graphX, X, 12, 62/3, 95/3, 45, 182/3, 236/3, ...
sunlet graph C_n circledot K_1X, X, 10, 97/6, 95/4, 158/5, 2429/60, 743/15, 297/5, ...
tetrahedral Johnson graphX, X, X, X, X, 415/3, 2345/6, 2800/3, 1981, 3850, 6985, 11990, ...
torus grid graph C_n square C_nX, X, 27, 206/3, 875/6, 1287/5, 12691/30, 66964/105, ...
transposition graphA2961940, 1, 12, 162, 3010, 81000, 3105396, 162469104, ...
triangular graphX, 0, 3, 27/2, 75/2, 165/2, 315/2, 273, 441, 675, 990, ...
triangular grid graphA0274803, 12, 30, 60, 105, 168, 252, 360, 495, 660, ...
web graphX, X, 45/2, 217/6, 635/12, 703/10, 1799/20, 110, ...
wheel graph W_nX, X, X, 6, 9, 25/2, 33/2, 21, 26, 63/2, 75/2, 44, 51, 117/2, ...
white bishop graph WB_(n,n)A296200X, 1, 5, 21, 47, 104, 182, 318, 490, 755, ...

Closed forms for some special classes are summarized in the following table. Here, H_n is a harmonic number, C_n is a Catalan number, Phi(z,s,a) is a Lerch transcendent, _pF_q is a generalized hypergeometric function, and s(n,m) is a signed Stirling number of the first kind.

graphHarary index
Andrásfai graph1/2(3n-1)(2n-1)
antiprism graph{2(2nH_(n/2-1)+3) for n even; 2n(2H_((n-1)/2)+1/(n+1)) for n odd
bishop graph B_(n,n)1/(48)[6n^4+16n^3-36n^2+8n+3-3(-1)^n]
black bishop graph BB_(n,n)1/(96)[6n^4+16n^3-30n^2+20n-15-3(-1)^n(2n^2+4n-5)]
cocktail party graph K_(n×2)1/2n(4n-3)
complete bipartite graph K_(m,n)1/4(m^2+n^2-m-n)+mn
complete bipartite graph K_(n,n)1/2n(3n-1)
complete graph K_n1/2n(n-1)
complete tripartite graph K_(n,n,n)3/4n(5n-1)
2n-crossed prism graph(8H_(n-1)-1/3)n+4
crown graph K_(n,n)-M1/6n(9n-7)
cycle graph C_n1/2(1+(-1)^n)+nH_(|_(n-1)/2_|)
empty graph K^__n0
gear graph G_n1/(24)n(17n+65)
grid graph P_n square P_n1/3n(2n+1)[(2n-1)(H_(n-3/2)-H_n+2ln2)-n+2]
=1/3n(2n+1)[(2n-1)(dlnC_(n-1))/(dn)-n+2]
halved cube graph 1/2Q_n-2^(n-1)H_n-2^(2n-1)Re[Phi(2,1,n+1)]
helm graph1/(24)n(17n+65)
hypercube graph Q_n2^(n-1)n_3F_2(1,1,1-n;2,2;-1)
Keller graph{0 for n=1; 4^n[4^n-1/2(3^n+n+1)]/2 otherwise
king graph Ki_(n,n)1/3(n-1)n(5n-1)
Möbius ladder M_n{n(4H_(n/2)-1) for n even; n(4H_((n-1)/2)-(n-3)/(n+1)) for n odd
Mycielski graph M_n{0 for n=1; 1/(48)(36-452^n+283^(n-1)+274^(n-1)) otherwise
pan graph{(n+2)H_(n/2)-2+2/(n+2) for n even; (n+2)H_((n-1)/2)+4/(n+1)-1 for n odd
path graph P_nn(H_n-1)
prism graph Y_n{4(nH_(n/2-1)-1/(n+2)+2)-n for n even; n(4H_((n-1)/2)-(n-3)/(n+1)) for n odd
queen graph Q_(n,n)1/(12)(n-1)n(3n^2+13n-2)
rook complement graph K_n square K_n^_1/2(n-1)n^3
rook graph K_n square K_n1/4(n-1)n^2(n+3)
star graph S_n1/4(n+2)(n-1)
sun graph1/6n(7n+3)
sunlet graph C_n circledot K_1{4nH_(n/2-1)-(5n)/2-8/(n+2)-4/(n+4)+12 for n even; 4nH_((n-1)/2)-(5n)/2-6/(n+1)-6/(n+3)+8 for n odd
tetrahedral Johnson graph1/(432)(n-3)(n-2)(n-1)n(2n^2+9n+40)
torus grid graph C_n square C_n{1/2n[4n^2(H_(n-1)-H_(n/2))+4n-3] for n even; 2n^3(H_(n-1)-H_((n-1)/2)) for n odd
transposition graph(n!)/2sum_(k=1)^(n-1)((-1)^ks(n,n-k))/k
triangular graph1/(16)(n-2)(n-1)n(n+5)
triangular grid graph1/2n(n+1)(n+2)
web graph{9nH_(n/2-1)-6n-(20)/(n+2)-(12)/(n+4)+29 for n even; 9nH_((n-1)/2)-(2n(3n^2+2n-15))/((n+1)(n+3)) for n odd
wheel graph W_n1/4(n-1)(n+4)
white bishop graph WB_(n,n)1/(96)[6n^4+16n^3-42n^2-4n+21+3(-1)^n(2n^2+4n-7)]

See also

Graph Distance Matrix, Topological Index

Explore with Wolfram|Alpha

References

Devillers, J. and Balaban, A. T. (Eds.). Topological Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands: Gordon and Breach, pp. 40, 111, 202, and 227, 1999.Diudea, M. V.; Ivanciuc, O.; Nikolić, S.; and Trinajstić, N. "Matrices of Reciprocal Distance, Polynomials and Derived Numbers." MATCH (Commun. Math. Comput. Chem.) 35, 41-64, 1997. https://match.pmf.kg.ac.rs/electronic_versions/Match35/match35_41-64.pdf.Ivanciuc, O.; Balaban, T.-S.; and Balaban, A. T. "Design of Topological Indices. Part 4. Reciprocal Distance Matrix, Related Local Vertex Invariants and Topological Indices." J. Math. Chem. 12, 309-318, 1993. https://doi.org/10.1007/BF01164642.Mercader, A.; Castro, E. A.; and Toropov, A. A. "Maximum Topological Distances Based Indices as Molecular Descriptors for QSPR. 4. Modeling the Enthalpy of Formation of Hydrocarbons from Elements." Int. J. Mol. Sci. 2, 121-132, 2001. https://doi.org/10.3390/i2020121.Mihalić, Z. and Trinajstić, N. "A Graph-Theoretical Approach to Structure-Property Relationships." J. Chem. Educ. 69, 701-712, 1992. https://doi.org/10.1021/ed069p701.Plavšić, D.; Nikolić, S.; Trinajstić, N.; and Mihalić, Z. "On the Harary Index for the Characterization of Chemical Graphs." J. Math. Chem. 12, 235-250, 1993. https://doi.org/10.1007/BF01164638.Sloane, N. J. A. Sequences A000217, A000326, A027480, A027611, A027612, A085740, A092364, A130658, A144945, A160046, A160047, A160050, A290343, A290344, A290347, A290348, A296057, A296189, A296190, A296191, A296192, A296193, A296194, A296196, A296197, A296198, and A296200 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Harary Index

Cite this as:

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

Subject classifications