Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
distance matrix; Laplacian; characteristic polynomial; eigenvalue
distance matrix; Laplacian; characteristic polynomial; eigenvalue
Summary:
The distance Laplacian of a connected graph $G$ is defined by $\mathcal {L} = {\rm Diag(Tr)}- \mathcal {D}$, where $\mathcal {D}$ is the distance matrix of $G$, and ${\rm Diag(Tr)}$ is the diagonal matrix whose main entries are the vertex transmissions in $G$. The spectrum of $\mathcal {L}$ is called the distance Laplacian spectrum of $G$. In the present paper, we investigate some particular distance Laplacian eigenvalues. Among other results, we show that the complete graph is the unique graph with only two distinct distance Laplacian eigenvalues. We establish some properties of the distance Laplacian spectrum that enable us to derive the distance Laplacian characteristic polynomials for several classes of graphs.
References:
[1] Aouchiche, M., Bonnefoy, J. M., Fidahoussen, A., Caporossi, G., Hansen, P., Hiesse, L., Lacheré, J., Monhait, A.: Variable neighborhood search for extremal graphs. XIV: The AutoGraphiX 2 system. Global Optimization. From Theory to Implementation Nonconvex Optim. Appl. 84 Springer, New York (2006), 281-310 L. Liberti et al. MR 2206957 | Zbl 1100.90052
[2] Aouchiche, M., Caporossi, G., Hansen, P.: Variable neighborhood search for extremal graphs. 20. Automated comparison of graph invariants. MATCH Commun. Math. Comput. Chem. 58 (2007), 365-384. MR 2357366 | Zbl 1274.05235
[3] Aouchiche, M., Hansen, P.: Two Laplacians for the distance matrix of a graph. Linear Algebra Appl. 439 (2013), 21-33. MR 3045220 | Zbl 1282.05086
[4] G. A. Baker, Jr.: Drum shapes and isospectral graphs. J. Math. Phys. 7 (1966), 2238-2242. DOI 10.1063/1.1704911 | Zbl 0203.27401
[5] Brouwer, A. E., Haemers, W. H.: Spectra of Graphs. Universitext Springer, Berlin (2012). MR 2882891 | Zbl 1231.05001
[6] Caporossi, G., Hansen, P.: Variable neighborhood search for extremal graphs. I: The AutoGraphiX system. Discrete Math. 212 (2000), 29-44 (J. Harant et al., eds.). DOI 10.1016/S0012-365X(99)00206-X | MR 1748671 | Zbl 0947.90130
[7] Collatz, L., Sinogowitz, U.: Spektren endlicher Grafen. Abh. Math. Semin. Univ. Hamb. 21 German (1957), 63-77. DOI 10.1007/BF02941924 | MR 0087952 | Zbl 0077.36704
[8] Cvetković, D. M.: Graphs and their spectra. Publ. Fac. Electrotech. Univ. Belgrade, Ser. Math. Phys. 354-356 (1971), 1-50. MR 0299508 | Zbl 0238.05102
[9] Cvetković, D. M., Doob, M., Gutman, I., Torgašev, A.: Recent Results in the Theory of Graph Spectra. Annals of Discrete Mathematics 36 North-Holland, Amsterdam (1988). MR 0926481 | Zbl 0634.05054
[10] Cvetković, D. M., Doob, M., Sachs, H.: Spectra of Graphs. Theory and Applications. J. A. Barth Verlag, Leipzig (1995). MR 1324340 | Zbl 0824.05046
[11] Cvetković, D. M., Rowlinson, P., Simić, S.: An Introduction to the Theory of Graph Spectra. London Mathematical Society Student Texts 75 Cambridge University Press, Cambridge (2010). MR 2571608 | Zbl 1211.05002
[12] Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298-305. MR 0318007 | Zbl 0265.05119
[13] Fujii, H., Katsuda, A.: Isospectral graphs and isoperimetric constants. Discrete Math. 207 (1999), 33-52. DOI 10.1016/S0012-365X(99)00133-8 | MR 1710481 | Zbl 1131.05309
[14] Günthard, H. H., Primas, H.: Zusammenhang von Graphtheorie und MO-Theorie von Molekeln mit Systemen konjugierter Bindungen. Helv. Chim. Acta 39 (1956), 1645-1653 German. DOI 10.1002/hlca.19560390623
[15] Haemers, W. H., Spence, E.: Enumeration of cospectral graphs. Eur. J. Comb. 25 (2004), 199-211. DOI 10.1016/S0195-6698(03)00100-8 | MR 2070541 | Zbl 1033.05070
[16] Halbeisen, L., Hungerbühler, N.: Generation of isospectral graphs. J. Graph Theory 31 (1999), 255-265. DOI 10.1002/(SICI)1097-0118(199907)31:3<255::AID-JGT7>3.0.CO;2-6 | MR 1688950 | Zbl 0932.05053
[17] Holton, D. A., Sheehan, J.: The Petersen Graph. Australian Mathematical Society Lecture Series 7 Cambridge University Press, Cambridge (1993). MR 1232658 | Zbl 0781.05001
[18] Marcus, M., Minc, H.: A Survey of Matrix Theory and Matrix Inequalities. Reprint of the 1969 edition. Dover Publications, New York (1992). MR 1215484
[19] McKay, B. D.: On the spectral characterisation of trees. Ars Comb. 3 (1977), 219-232. MR 0543669 | Zbl 0404.05045
[20] Merris, R.: Large families of Laplacian isospectral graphs. Linear Multilinear Algebra 43 (1997), 201-205. DOI 10.1080/03081089708818525 | MR 1613203 | Zbl 0887.05036
[21] Merris, R.: Laplacian matrices of graphs: A survey. Second Conference of the International Linear Algebra Society, Lisbon, 1992 (J. D. da Silva et al., eds.) Linear Algebra Appl. 197-198 (1994), 143-176. MR 1275613 | Zbl 0802.05053
[22] Mohar, B.: Graph Laplacians. Topics in Algebraic Graph Theory Encyclopedia of Mathematics and its Applications 102 Cambridge University Press, Cambridge (2004), 113-136 L. W. Beineke et al. MR 2125091 | Zbl 1161.05334
[23] Schwenk, A. J.: Almost all trees are cospectral. New Directions in the Theory of Graphs. Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971 Academic Press, New York (1973), 275-307 F. Harary. MR 0384582
[24] Tan, J.: On isospectral graphs. Interdiscip. Inf. Sci. 4 (1998), 117-124. MR 1664212 | Zbl 0926.05027
[25] Dam, E. R. van, Haemers, W. H.: Which graphs are determined by their spectrum?. Special Issue on the Combinatorial Matrix Theory Conference, Pohang, 2002 Linear Algebra Appl. 373 (2003), 241-272. MR 2022290
Search
Partner of
