×

Distance spectral radius of trees with given matching number. (English) Zbl 1208.05018

Summary: The distance spectral radius \(\rho (G)\) of a graph \(G\) is the largest eigenvalue of the distance matrix \(D(G)\). Recently, many researches proposed the use of \(\rho (G)\) as a molecular structure descriptor of alkanes. In this paper, we introduce general transformations that decrease distance spectral radius and characterize \(n\)-vertex trees with given matching number \(m\) which minimize the distance spectral radius. The extremal tree \(A(n,m)\) is a spur, obtained from the star graph \(S_{n - m+1}\) with \(n - m+1\) vertices by attaching a pendent edge to each of certain \(m - 1\) non-central vertices of \(S_{n - m+1}\). The resulting trees also minimize the spectral radius of adjacency matrix, Hosoya index, Wiener index and graph energy in the same class of trees. In conclusion, we pose a conjecture for the maximal case based on the computer search among trees on \(n\leq 24\) vertices. In addition, we found the extremal tree that uniquely maximizes the distance spectral radius among \(n\)-vertex trees with perfect matching and fixed maximum degree \(\varDelta \).

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)

Software:

Mathematica
PDFBibTeX XMLCite
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] Bapat, R. B.; Kirkland, S. J.; Neumann, M., On distance matrices and Laplacians, Linear Algebra Appl., 401, 193-209 (2005) · Zbl 1064.05097
[3] Consonni, V.; Todeschini, R., New spectral indices for molecule description, MATCH Commun. Math. Comput. Chem., 60, 3-14 (2008) · Zbl 1273.92080
[4] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2001), MIT Press · Zbl 1047.68161
[5] Cvetković, D.; Doob, M.; Sachs, H., Spectra of graphs — Theory and Application (1995), Johann Ambrosius Barth Verlag · Zbl 0824.05046
[6] Dankelmann, P., Average distance and independence number, Discrete Appl. Math., 51, 75-83 (1994) · Zbl 0803.05020
[7] Dobrynin, A.; Entringer, R.; Gutman, I., Wiener index of trees: theory and applications, Acta Appl. Math., 66, 211-249 (2001) · Zbl 0982.05044
[8] Du, Z.; Zhou, B., Minimum Wiener indices of trees and unicyclic graphs of given matching number, MATCH Commun. Math. Comput. Chem., 63, 101-112 (2010) · Zbl 1299.05083
[9] Guo, J. M., On the minimal energy ordering of trees with perfect matchings, Discrete Appl. Math., 156, 2598-2605 (2008) · Zbl 1214.05122
[10] Gutman, I., The energy of a graph: old and new results, (Betten, A.; Kohnert, A.; Laue, R.; Wassermann, A., Algebraic Combinatorics and Applications (2001), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0974.05054
[11] Gutman, I.; Medeleanu, M., On the structure-dependence of the largest eigenvalue of the distance matrix of an alkane, Indian J. Chem. A, 37, 569-573 (1998)
[12] Hou, Y., On acyclic systems with minimal Hosoya index, Discrete Appl. Math., 119, 251-257 (2002) · Zbl 0999.05020
[13] Hou, Y.; Li, J., Bounds on the largest eigenvalues of trees with a given size of matching, Linear Algebra Appl., 342, 203-217 (2002) · Zbl 0992.05055
[14] 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
[15] Indulal, G.; Gutman, I., On the distance spectra of some graphs, Math. Commun., 13, 123-131 (2008) · Zbl 1140.05026
[16] Indulal, G.; Gutman, I.; Vijayakumar, A., On distance energy of graphs, MATCH Commun. Math. Comput. Chem., 60, 461-472 (2008) · Zbl 1199.05226
[17] Merris, R., The distance spectrum of a tree, J. Graph Theory, 14, 365-369 (1990) · Zbl 0734.05037
[18] 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)
[19] Ou, J., Maximal Hosoya index and extremal acyclic molecular graphs without perfect matching, Appl. Math. Lett., 19, 652-656 (2006) · Zbl 1119.05104
[20] Ou, J., On extremal unicyclic molecular graphs with maximal Hosoya index, Discrete Appl. Math., 157, 391-397 (2009) · Zbl 1200.05241
[21] Ramane, H. S.; Gutman, I.; Revankar, D. S., Distance equienergetic graphs, MATCH Commun. Math. Comput. Chem., 60, 473-484 (2008) · Zbl 1199.05096
[22] Stevanović, D.; Ilić, A., Distance spectral radius of trees with fixed maximum degree, Electron. J. Linear Algebra, 20, 168-179 (2010) · Zbl 1189.05050
[23] 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
[24] Subhi, R.; Powers, D., The distance spectrum of the path \(P_n\) and the first distance eigenvector of connected graphs, Linear Multilinear Algebra, 28, 75-81 (1990) · Zbl 0728.05043
[25] Wolfram Research, Mathematica Edition: Version 7.0, Wolfram Research Inc., Champaign, Illinois, 2008.; Wolfram Research, Mathematica Edition: Version 7.0, Wolfram Research Inc., Champaign, Illinois, 2008.
[26] Zhang, F.; Li, H., On acyclic conjugated molecules with minimal energies, Discrete Appl. Math., 92, 71-84 (1999) · Zbl 0920.92037
[27] Zhou, B., On the largest eigenvalue of the distance matrix of a tree, MATCH Commun. Math. Comput. Chem., 58, 657-662 (2007) · Zbl 1199.05102
[28] Zhou, B.; Trinajstić, N., On the largest eigenvalue of the distance matrix of a connected graph, Chem. Phys. Lett., 447, 384-387 (2007)
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.