Spectral properties of the eccentricity matrix of graphs. (English) Zbl 1439.05146
Summary: The eccentricity matrix \(\mathcal{E}(G)\) of a graph \(G\) is derived from the distance matrix by keeping for each row and each column only the largest distances and leaving zeros in the remaining ones. The \(\mathcal{E}\)-eigenvalues of a graph \(G\) are those of its eccentricity matrix \(\mathcal{E}(G)\). The \(\mathcal{E}\)-spectrum of \(G\) is the multiset of its \(\mathcal{E}\)-eigenvalues, where the largest one is the \(\mathcal{E}\)-spectral radius. In this paper, we proceed to study the algebraic properties of the \(\mathcal{E}\)-spectrum. In particular, we give a condition to connected graphs with cut vertices so that their eccentricity matrices are irreducible. The latter partially answers the problem given in [J. Wang et al., ibid. 251, 299–309 (2018; Zbl 1401.05102)]. We determine the lower and upper bounds for the \(\mathcal{E}\)-spectral radius of graphs, and we identify the corresponding extremal graphs. Finally, we investigate the least \(\mathcal{E}\)-eigenvalue of graphs, and list the \(\mathcal{E}\)-eigenvalues of trees with order 8.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C12 | Distance in graphs |
| 05C35 | Extremal problems in graph theory |
Citations:
Zbl 1401.05102References:
| [1] | Brouwer, A. E.; Cioabǎ, S. M.; Ihringer, F.; McGinnis, M., The smallest eigenvalues of Hamming graphs, J. Comb. Theory B, 133, 88-121 (2018) · Zbl 1397.05098 |
| [2] | Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of Graphs Theory and Applications (1980), Academic Press: Academic Press New York, San Francisco, London · Zbl 0458.05042 |
| [3] | Cvetković, D.; Lepović, M.; Rowlinson, P.; Simić, S. K., The maximal exceptional graphs, J. Comb. Theory B, 86, 347-363 (2002) · Zbl 1028.05063 |
| [4] | Cvetković, D.; Rowlinson, P., The largest eigenvalue of a graph: A survey, Linear Multilinear Algebr., 28, 3-33 (1990) · Zbl 0744.05031 |
| [5] | Cvetković, D.; Rowlinson, P.; Simić, S. K., Spectral generalizations of line graphs, (On Graphs with Least Eigenvalue -2 (2004), Cambridge University Press) · Zbl 1061.05057 |
| [6] | van Dam, E. R., Graphs with few eigenvalues, (An Interplay Between Combinatorics and Algebra. An Interplay Between Combinatorics and Algebra, Center Dissertation Series, vol. 20 (1996), Tilburg University) |
| [7] | van Dam, E. R.; Haemers, W. H., Which graphs are determined by their spectra?, Linear Algebra Appl., 373, 241-272 (2003) · Zbl 1026.05079 |
| [8] | van Dam, E. R.; Haemers, W. H., Developments on spectral characterizations of graphs, Discrete Math., 309, 576-586 (2009) · Zbl 1205.05156 |
| [9] | Dehmer, M.; Shi, Y. T., The uniqueness of \(D_{\operatorname{MAX}} \)-matrix graph invariants, PLoS ONE, 9, Article e83868 pp. (2014) |
| [10] | Dress, A.; Stevanović, D., Hoffman-type identities, Appl. Math. Lett., 16, 297-302 (2003) · Zbl 1041.05048 |
| [11] | Ellingham, M. N.; Zha, X., The spectral radius of graphs on surface, J. Comb. Theory B, 78, 45-56 (2000) · Zbl 1028.05065 |
| [12] | Fan, Y.-Z.; Zhang, F.-F.; Wang, Y., The least eigenvalue of the complements of trees, Linear Algebra Appl., 435, 2150-2155 (2011) · Zbl 1222.05156 |
| [13] | Godsil, C. D., Algebraic Combinatorics (1993), Chapman and Hall · Zbl 0814.05075 |
| [14] | Günthard, Hs. H.; Primas, H., Zusammenhang von graphtheorie und mo-theotie von molekeln mit systemen konjugierter bindungen, Helv. Chim. Acta, 39, 1645-1653 (1956) |
| [15] | Guo, J.-M., The Laplacian spectral radii of unicyclic and bicyclic graphs with \(n\) vertices and \(k\) pendant vertices, Sci. China Math., 53, 2135-2142 (2010) · Zbl 1210.05079 |
| [16] | Hoffman, A. J., On the polynomial of a graph, Amer. Math. Monthly, 70, 30-36 (1963) · Zbl 0112.14901 |
| [17] | Horn, R. A.; Johnson, C. R., Matrix Analysis (1986), Cambridge University Press |
| [18] | Jin, Y.-L.; Zhang, X.-D., Complete multipartite graphs are determined by their distance spectra, Linear Algebra Appl., 448, 285-291 (2014) · Zbl 1285.05114 |
| [19] | Koolen, J. H.; Yang, J. Y.; Yang, Q. Q., On graphs with smallest eigenvalue at least \(- 3\) and their lattices, Adv. Math., 338, 847-864 (2018) · Zbl 1396.05071 |
| [20] | Li, J.; Shiu, W. C.; Chan, W. H.; Chang, A., On the spectral radius of graphs with connectivity at most \(k\), J. Math. Chem., 46, 340-346 (2009) · Zbl 1310.05138 |
| [21] | Ma, Y.; Cao, S.; Shi, Y.; Gutman, I.; Dehmer, M.; Furtula, B., From the connectivity index to various Randić-type descriptors, MATCH Commun. Math. Comput. Chem., 80, 85-106 (2018) · Zbl 1468.05136 |
| [22] | I. Mahato, R. Gurusamy, M.R. Kannan, S. Arockiaraj, Spectra of eccentricity matrices of graphs, arXiv:1902.02608v1. · Zbl 1447.05126 |
| [23] | Randić, M., \( D_{\operatorname{MAX}} \)-MAtrix of dominant distances in a graph, MATCH Commun. Math. Comput. Chem., 70, 221-238 (2013) · Zbl 1299.05106 |
| [24] | Stevanović, D., Spectral Radius of Graphs (2015), Academic Press: Academic Press Amsterdam · Zbl 1309.05001 |
| [25] | Tait, M.; Tobin, J., Three conjectures in extremal spectral graph theory, J. Comb. Theory B, 126, 137-161 (2017) · Zbl 1368.05098 |
| [26] | Wang, J. F.; Lu, M.; Belardo, F.; Randić, M., The anti-adjacency matrix of a graph: eccentricity matrix, Discrete Appl. Math., 251, 299-309 (2018) · Zbl 1401.05102 |
| [27] | J.F. Wang, M. Lu, M. Brunetti, L. Lu, X.Y. Huang, Self-centered graphs and eccentricity matrix, submitted. · Zbl 1491.05127 |
| [28] | Wang, J. F.; Lu, L.; Randić, M.; Li, G. Z., Graph energy based on the eccentricity matrix, Discrete Math., 342, 2636-2646 (2019) · Zbl 1416.05183 |
| [29] | Zhang, L. Z.; Tian, F., Extremal hexagonal chains concerning largest eigenvalue, Sci. China A, 44, 1089-1097 (2001) · Zbl 0999.05074 |
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.
