×

Distance spectral spread of a graph. (English) Zbl 1251.05100

Summary: Let \(D(G)=(d_{i,j})_{n\times n}\) denote the distance matrix of a connected graph \(G\) with order \(n\), where \(d_{ij}\) is equal to the distance between vertices \(v_{i}\) and \(v_{j}\) in G. The value \(D_{i}=\sum_{j=1}^{n}d_{ij}(i=1,2, \dots ,n\)) is called the distance degree of vertex \(v_{i}\). Denote by \(\rho (G),\rho_{n}(G)\) the largest eigenvalue and the smallest eigenvalue of \(D(G)\) respectively. The distance spectral spread of a graph \(G\) is defined to be \(S_{D}(G)=\rho (G) - \rho_{n}(G)\).
In this paper, some lower bounds on \(S_{D}(G)\) are given in terms of distance degrees, the largest vertex degree and clique number; the spreads of \(K_{n}\), \(K_{\lfloor \frac {1}{2}\rfloor,\lceil \frac {1}{2} \rceil}\), \(K_{n - \alpha }\nabla \alpha K_{1}\), \(K_{1,n - 1}\) are proved to be the least among all connected graphs with \(n\) vertices, all bipartite graphs with \(n\) vertices, all the graphs with both \(n\) vertices and independent number \(\alpha \), all trees with \(n\) vertices respectively.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C35 Extremal problems in graph theory
05C12 Distance in graphs
Full Text: DOI

References:

[1] Balaban, A. T.; Ciubotariu, D.; Medeleanu, M., Topological indices and real number vertex invariants based on graph eigenvalues or eigenvectors, J. Chem. Inf. Comput. Sci., 31, 517-523 (1991)
[2] Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of Graphs Theory and Application (1995), Johann Ambrosius Barth Verlag Heidelberg: Johann Ambrosius Barth Verlag Heidelberg Leipzig · Zbl 0824.05046
[3] Gregory, D. A.; Hershkowitz, D.; Kirkland, S. J., The spread of the spectrum of a graph, Linear Algebra Appl., 332-334, 23-35 (2001) · Zbl 0978.05049
[4] Gutman, I.; Medeleau, M., On the structure-dependence of the largest eigenvalue of distance matrix of an alkane, Indian J. Chem. A, 37, 569-573 (1998)
[5] Haemers, W. H., Interlacing eigenvalues and graphs, Linear Algebra Appl., 227-228, 593-616 (1995) · Zbl 0831.05044
[6] Ilić, A., Distance spectral radius of trees with given matching number, Discrete Appl. Math., 158, 1799-1806 (2010) · Zbl 1208.05018
[7] Indulal, G., Sharp bounds on the distance spectral radius and the distance energy of graphs, Linear Algebra Appl., 430, 106-113 (2009) · Zbl 1165.05019
[8] Johnson, C. R.; Kumar, R.; Wolkowicz, H., Lower bounds for the spread of a matrix, Linear Algebra Appl., 71, 161-173 (1985) · Zbl 0578.15013
[9] Liu, M. H.; Liu, B. L., The signless Laplacian spread, Linear Algebra Appl., 432, 505-514 (2010) · Zbl 1206.05064
[10] Mihalić, Z.; Veljan, D.; Amić, D.; Nikolić, S.; Plavšić, D.; Trinajstić, N., The distance matrix in chemistry, J. Math. Chem., 11, 223-258 (1992)
[11] Minc, H., Nonnegative Matrices (1988), John Wiley & Sons Inc.: John Wiley & Sons Inc. New York · Zbl 0638.15008
[12] Mirsky, L., The spread of a matrix, Mathematica, 3, 127-130 (1956) · Zbl 0073.00903
[13] Stevanović, D.; Ilić, A., Distance spectral radius of trees with fixed maximum degree, Electron. J. Linear Algebra, 20, 168-179 (2010) · Zbl 1189.05050
[14] Stevanović, D.; Indulal, G., The distance spectrum and energy of the compositions of regular graphs, Appl. Math. Lett., 22, 1136-1140 (2009) · Zbl 1179.05040
[15] Zhang, X. L.; Godsil, C., Connectivity and minimal distance spectral radius, Linear Multilinear Algebra, 1-10 (2011), iFirst
[16] Zhou, B.; Ilić, A., On distance spectral radius and distance energy of graphs, Match Commun. Math. Comput. Chem., 64, 261-280 (2010) · Zbl 1265.05437
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.