TOPICS
Search

Stability Index

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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

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

is defined by

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

where |_n_| denotes the floor function.

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.

graph classOEISZ^_(G_1), Z^_(G_2), ...
Andrásfai graph2, 2, 70, 312, 2176, 16054, 69882, ...
antiprism graphX, X, 13, 117, 606, 1453, 5013, 26141, 91867, ...
Apollonian network10, 56, 11757, 108238346932, ...
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_n0, 2, 2, 10, 24, 66, 160, 386, 896, 2050, ...
complete tripartite graph K_(n,n,n)2, 13, 54, 49, 250, 109, ...
crossed prism graph80, 1280, 11520, 128000, 1310720, 13844480, ...
crown graphX, X, 20, 80, 272, 832, 2368, 6400, 16640, ...
cube-connected cycle graphX, X, 702672, 2312110080000000, ...
cycle graph C_nX, X, 2, 5, 2, 20, 2, 45, 2, 125, 2, 320, 2, ...
empty graph K^__nA0000350, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...
folded cube graph2, 10, 17, 150806, 1129150390625, ...
gear graphA000004X, X, 0, 0, 0, 0, 0, 0, ...
grid graph P_n square P_n0, 5, 0, 4176, 0, 390590941, 0, 4363974545574685, ...
grid graph P_n square P_n square P_n0, 80, 0, 473138263916015625, 0, ...
halved cube graph0, 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 graph0, 2, 2, 432, 2440488, 113920311278592, ...
odd graph O_n0, 2, 424, 46757736448, ...
pan graphX, X, 6, 0, 16, 0, 42, 0, 110, 0, ...
path graph0, 2, 0, 5, 0, 13, 0, 34, 0, 89, 0, 233, ...
permutation star graph PS_n0, 2, 20, 1250000, ...
prism graph Y_nX, X, 22, 80, 204, 500, 1684, 5120, 14062, ...
rook graph K_n square K_n5, 112, 492593, 77149243008, 254773522981613013, ...
star graph S_nA2374200, 2, 0, 4, 0, 6, 0, 8, 0, 10, 0, ...
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, 0, 2, 13, 748, 362144, 2185830840, ...
web graphX, X, 333, 56, 6253, 566, 120213, 2982, 2202832, ...
wheel graph W_nX, X, X, 10, 8, 26, 48, 78, 144, 220, 500, 650, ...

Closed forms are summarized in the following table, where F_n is a Fibonacci number.

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_n2^(n-2)(n-2)+(-1)^n+1
crossed prism graph(6+2sqrt(5))^n+(6-2sqrt(5))^n-(-1)^n2^(2n+1)
crown graph2^(n-1)(n^2-2n+2)
cycle graph C_n{2 for n odd; 5F_(n/2)^2 for n even
empty graph K^__n1/2(1+(-1)^n)
gear graph0
pan graph{0 for n even; 2F_(n+1) for n odd
path graph P_n{0 for n odd; F_(n+1) for n even
star graph S_n1/2(1+(-1)^n)n
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.Sloane, N. J. A. Sequences A000004/M0000, A000035/M0001, A000079/M1129, A000129/M1413, A002522, A138573, and A237420 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