Some properties of the distance Laplacian eigenvalues of a graph

Aouchiche, Mustapha   ; Hansen, Pierre

Czechoslovak Mathematical Journal, Tome 64 (2014) no. 3, pp. 751-761

Abstract (VO)

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.

Détail

DOI : 10.1007/s10587-014-0129-2

Classification : 05C12, 05C31, 05C50, 05C76
Keywords: distance matrix; Laplacian; characteristic polynomial; eigenvalue

Bibliographie

[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 | Zbl

[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 | Zbl

[3] Aouchiche, M., Hansen, P.: Two Laplacians for the distance matrix of a graph. Linear Algebra Appl. 439 (2013), 21-33. | MR | Zbl

[4] G. A. Baker, Jr.: Drum shapes and isospectral graphs. J. Math. Phys. 7 (1966), 2238-2242. | DOI | Zbl

[5] Brouwer, A. E., Haemers, W. H.: Spectra of Graphs. Universitext Springer, Berlin (2012). | MR | Zbl

[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 | MR | Zbl

[7] Collatz, L., Sinogowitz, U.: Spektren endlicher Grafen. Abh. Math. Semin. Univ. Hamb. 21 German (1957), 63-77. | DOI | MR | Zbl

[8] Cvetković, D. M.: Graphs and their spectra. Publ. Fac. Electrotech. Univ. Belgrade, Ser. Math. Phys. 354-356 (1971), 1-50. | MR | Zbl

[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 | Zbl

[10] Cvetković, D. M., Doob, M., Sachs, H.: Spectra of Graphs. Theory and Applications. J. A. Barth Verlag, Leipzig (1995). | MR | Zbl

[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 | Zbl

[12] Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298-305. | MR | Zbl

[13] Fujii, H., Katsuda, A.: Isospectral graphs and isoperimetric constants. Discrete Math. 207 (1999), 33-52. | DOI | MR | Zbl

[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

[15] Haemers, W. H., Spence, E.: Enumeration of cospectral graphs. Eur. J. Comb. 25 (2004), 199-211. | DOI | MR | Zbl

[16] Halbeisen, L., Hungerbühler, N.: Generation of isospectral graphs. J. Graph Theory 31 (1999), 255-265. | DOI | MR | Zbl

[17] Holton, D. A., Sheehan, J.: The Petersen Graph. Australian Mathematical Society Lecture Series 7 Cambridge University Press, Cambridge (1993). | MR | Zbl

[18] Marcus, M., Minc, H.: A Survey of Matrix Theory and Matrix Inequalities. Reprint of the 1969 edition. Dover Publications, New York (1992). | MR

[19] McKay, B. D.: On the spectral characterisation of trees. Ars Comb. 3 (1977), 219-232. | MR | Zbl

[20] Merris, R.: Large families of Laplacian isospectral graphs. Linear Multilinear Algebra 43 (1997), 201-205. | DOI | MR | Zbl

[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 | Zbl

[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 | Zbl

[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

[24] Tan, J.: On isospectral graphs. Interdiscip. Inf. Sci. 4 (1998), 117-124. | MR | Zbl

[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