TOPICS
Search

Stability Index

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The stability index Z^_(G) of a graph G on n vertices, with monic adjacency characteristic polynomial

p_G(x)=det(xI-A)=sum_(k=0)^nc_kx^(n-k),
(1)

is defined by

Z^_(G)=sum_(k=0)^(|_n/2_|)|c_(2k)|,
(2)

where A is the adjacency matrix, I is the identity matrix, and |_n/2_| denotes the floor function (Ivanciuc and Balaban 1994, p. 128). Since c_0=1, every graph has Z^_(G)>=1.

When G is a bipartite graph, its graph spectrum consists of real numbers and is symmetric about zero. Consequently,

p_G(x)=x^rproduct_(j)(x^2-lambda_j^2),
(3)

where r is the multiplicity of 0 and the +/-lambda_j are the nonzero graph eigenvalues. The even-indexed coefficients then satisfy c_(2k)=(-1)^k|c_(2k)|. Evaluation at the imaginary unit therefore gives

p_G(i)=i^nZ^_(G)
(4)
={(-1)^(n/2)Z^_(G) for n even; i(-1)^((n-1)/2)Z^_(G) for n odd.
(5)

It follows that for a bipartite graph the stability index is the complex modulus Z^_(G)=|p_G(i)|, including for odd n, when p_G(i) is purely imaginary. For even n, the first case is equivalently Z^_(G)=(-1)^(n/2)p_G(i).

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 stability 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. The web graph row uses the construction from Y_(n+1,3) with the outer graph cycle removed. The halved cube graph row refers to a single parity component.

graph classOEISZ^_(G_1), Z^_(G_2), ...
Andrásfai graph2, 11, 70, 397, 2176, 12003, 69882, ...
antiprism graphX, X, 13, 117, 606, 1453, 5013, 26141, 91867, ...
Apollonian network10, 21, 11757, 122041306642, ...
centipede graphA0001292, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, ...
cocktail party graph K_(n×2)1, 5, 13, 73, 281, 1101, 4005, 14225, 49201, ...
complete bipartite graph K_(n,n)A0025222, 5, 10, 17, 26, 37, 50, 65, 82, 101, ...
complete graph K_n1, 2, 4, 10, 26, 66, 162, 386, 898, 2050, ...
complete tripartite graph K_(n,n,n)4, 13, 28, 49, 76, 109, ...
crossed prism graphX, X, X, 80, X, 1280, X, 11520, X, 128000, X, 1310720, X, 13844480, ...
crown graph1, 4, 20, 80, 272, 832, 2368, 6400, 16640, ...
cube-connected cycle graphX, X, 702672, 2312110080000000, ...
cycle graph C_nX, X, 4, 5, 11, 20, 29, 45, 76, 125, 199, 320, 521, ...
empty graph K^__n1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
folded cube graph2, 10, 17, 150806, 1129150390625, ...
gear graphX, X, 32, 81, 250, 704, 2028, 5733, ...
grid graph P_n square P_n1, 5, 81, 4176, 703040, 390590941, 717681759921, 4363974545574685, ...
grid graph P_n square P_n square P_n1, 80, 10097379, 473138263916015625, ...
halved cube graph1, 2, 10, 73, 1716177, 990952398727038, ...
hypercube graph Q_n2, 5, 80, 10625, 2662400000, 27254945465087890625, ...
ladder graph L_nA1385732, 5, 16, 45, 130, 377, 1088, 3145, 9090, ...
ladder rung graphA0000792, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ...
Möbius ladder M_nX, X, 10, 70, 250, 580, 1690, 4870, 13690, 40650, 118810, ...
Mycielski graph1, 2, 11, 382, 809824, 31677223961002, ...
odd graph O_n1, 4, 424, 32394343808, ...
pan graphX, X, 6, 8, 16, 28, 42, 66, 110, 180, ...
path graph1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...
permutation star graph PS_n1, 2, 20, 1250000, ...
prism graph Y_nX, X, 22, 80, 204, 500, 1684, 5120, 14062, ...
rook graph K_n square K_n1, 5, 412, 492593, 82184054096, 254773522981613013, ...
star graph S_n1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
sun graphX, X, 23, 52, 115, 202, 761, 4390, 20771, ...
sunlet graph C_n circledot K_1X, X, 14, 32, 82, 200, 478, 1152, 2786, 6728, ...
tetrahedral Johnson graphX, X, X, X, X, 88567324, 6545276817256, ...
triangular graphX, 1, 4, 13, 748, 627917, 2259401704, ...
web graphX, X, 333, 1484, 6253, 27593, 120213, 512483, 2202832, ...
wheel graph W_nX, X, X, 10, 9, 26, 44, 78, 117, 220, 375, 650, ...

Closed forms are summarized in the following table, where F_n is a Fibonacci number. The crossed prism graph formula applies to even n>=4, while the cycle graph, gear graph, pan graph, and sunlet graph formulas apply to n>=3.

graphstability index
cocktail party graph K_(n×2)1/6(3^n(2n-3)+3(-1)^n(2n-1)+12)
complete bipartite graph K_(n,n)n^2+1
complete graph K_n{1 for n=1; 2+(n-2)2^(n-2) for n>=2
crossed prism graph(6+2sqrt(5))^(n/2)+(6-2sqrt(5))^(n/2)-(-1)^(n/2)2^(n+1)
crown graph2^(n-1)(n^2-2n+2)
cycle graph C_n{F_(n-1)+F_(n+1) for n odd; 5F_(n/2)^2 for n even
empty graph K^__n1
gear graph(n+5)F_n^2
pan graph{5F_(n/2)^2+F_n for n even; 2F_(n+1) for n odd
path graph P_nF_(n+1)
star graph S_nn
sunlet graph C_n circledot K_1(1-sqrt(2))^n+(1+sqrt(2))^n-2cos(1/2npi)

See also

Hosoya Index, Matching Polynomial

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. 27-28 and 105, 1999.Ivanciuc, O. and Balaban, A. T. "Design of Topological Indices. Part 5. Precision and Error in Computing Graph Theoretic Invariants for Molecules Containing Heteroatoms and Multiple Bonds." Match 30, 117-139, 1994. https://match.pmf.kg.ac.rs/electronic_versions/Match30/match30_117-139.pdf.Sloane, N. J. A. Sequences A000079/M1129, A000129/M1413, A002522, and A138573 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Stability Index

Cite this as:

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

Subject classifications