Abstract
The distance Laplacian of a connected graph G is defined by \(\mathcal{L} = Diag(Tr) - \mathcal{D}\), where \(\mathcal{D}\) is the distance matrix of G, and 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Aouchiche, J. M. Bonnefoy, A. Fidahoussen, G. Caporossi, P. Hansen, L. Hiesse, J. Lacheré, A. Monhait: Variable neighborhood search for extremal graphs. XIV: The AutoGraphiX 2 system. Global Optimization. From Theory to Implementation (L. Liberti et al., eds.). Nonconvex Optim. Appl. 84, Springer, New York, 2006, pp. 281–310.
M. Aouchiche, G. Caporossi, P. Hansen: Variable neighborhood search for extremal graphs. 20. Automated comparison of graph invariants. MATCH Commun. Math. Comput. Chem. 58 (2007), 365–384.
M. Aouchiche, P. Hansen: Two Laplacians for the distance matrix of a graph. Linear Algebra Appl. 439 (2013), 21–33.
G. A. Baker, Jr.: Drum shapes and isospectral graphs. J. Math. Phys. 7 (1966), 2238–2242.
A. E. Brouwer, W. H. Haemers: Spectra of Graphs. Universitext, Springer, Berlin, 2012.
G. Caporossi, P. Hansen: Variable neighborhood search for extremal graphs. I: The AutoGraphiX system. (J. Harant et al., eds.), Discrete Math. 212 (2000), 29–44.
L. Collatz, U. Sinogowitz: Spektren endlicher Grafen. Abh. Math. Semin. Univ. Hamb. 21 (1957), 63–77. (In German.)
D. M. Cvetković: Graphs and their spectra. Publ. Fac. Electrotech. Univ. Belgrade, Ser. Math. Phys. 354-356 (1971), 1–50.
D. M. Cvetković, M. Doob, I. Gutman, A. Torgašev: Recent Results in the Theory of Graph Spectra. Annals of Discrete Mathematics 36, North-Holland, Amsterdam, 1988.
D. M. Cvetković, M. Doob, H. Sachs: Spectra of Graphs. Theory and Applications. J. A. Barth Verlag, Leipzig, 1995.
D. M. Cvetković, P. Rowlinson, S. Simić: An Introduction to the Theory of Graph Spectra. London Mathematical Society Student Texts 75, Cambridge University Press, Cambridge, 2010.
M. Fiedler: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298–305.
H. Fujii, A. Katsuda: Isospectral graphs and isoperimetric constants. Discrete Math. 207 (1999), 33–52.
H. H. Günthard, H. Primas: Zusammenhang von Graphtheorie und MO-Theorie von Molekeln mit Systemen konjugierter Bindungen. Helv. Chim. Acta 39 (1956), 1645–1653. (In German.)
W. H. Haemers, E. Spence: Enumeration of cospectral graphs. Eur. J. Comb. 25 (2004), 199–211.
L. Halbeisen, N. Hungerbühler: Generation of isospectral graphs. J. Graph Theory 31 (1999), 255–265.
D. A. Holton, J. Sheehan: The Petersen Graph. Australian Mathematical Society Lecture Series 7, Cambridge University Press, Cambridge, 1993.
M. Marcus, H. Minc: A Survey of Matrix Theory and Matrix Inequalities. Reprint of the 1969 edition. Dover Publications, New York, 1992.
B. D. McKay: On the spectral characterisation of trees. Ars Comb. 3 (1977), 219–232.
R. Merris: Large families of Laplacian isospectral graphs. Linear Multilinear Algebra 43 (1997), 201–205.
R. Merris: 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.
B. Mohar: Graph Laplacians. Topics in Algebraic Graph Theory (L. W. Beineke et al., eds.). Encyclopedia of Mathematics and its Applications 102, Cambridge University Press, Cambridge, 2004, pp. 113–136.
A. J. Schwenk: Almost all trees are cospectral. New Directions in the Theory of Graphs. Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971 (F. Harary, ed.). Academic Press, New York, 1973, pp. 275–307.
J. Tan: On isospectral graphs. Interdiscip. Inf. Sci. 4 (1998), 117–124.
E. R. vanDam, W. H. Haemers: Which graphs are determined by their spectrum? Special Issue on the Combinatorial Matrix Theory Conference, Pohang, 2002, Linear Algebra Appl. 373 (2003), 241–272.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Aouchiche, M., Hansen, P. Some properties of the distance Laplacian eigenvalues of a graph. Czech Math J 64, 751–761 (2014). https://doi.org/10.1007/s10587-014-0129-2
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10587-014-0129-2