Some properties of the distance Laplacian eigenvalues of a graph

Mustapha Aouchiche; Pierre Hansen

Czechoslovak Mathematical Journal (2014)

  • Volume: 64, Issue: 3, page 751-761
  • ISSN: 0011-4642

Abstract

top
The distance Laplacian of a connected graph G is defined by ℒ = Diag ( Tr ) - 𝒟 , where 𝒟 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 ℒ 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.

How to cite

top

Aouchiche, Mustapha, and Hansen, Pierre. "Some properties of the distance Laplacian eigenvalues of a graph." Czechoslovak Mathematical Journal 64.3 (2014): 751-761. <http://eudml.org/doc/262154>.

@article{Aouchiche2014,
abstract = {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.},
author = {Aouchiche, Mustapha, Hansen, Pierre},
journal = {Czechoslovak Mathematical Journal},
keywords = {distance matrix; Laplacian; characteristic polynomial; eigenvalue; distance matrix; Laplacian; characteristic polynomial; eigenvalue},
language = {eng},
number = {3},
pages = {751-761},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Some properties of the distance Laplacian eigenvalues of a graph},
url = {http://eudml.org/doc/262154},
volume = {64},
year = {2014},
}

TY - JOUR
AU - Aouchiche, Mustapha
AU - Hansen, Pierre
TI - Some properties of the distance Laplacian eigenvalues of a graph
JO - Czechoslovak Mathematical Journal
PY - 2014
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 64
IS - 3
SP - 751
EP - 761
AB - 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.
LA - eng
KW - distance matrix; Laplacian; characteristic polynomial; eigenvalue; distance matrix; Laplacian; characteristic polynomial; eigenvalue
UR - http://eudml.org/doc/262154
ER -

References

top
  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. (2006) Zbl1100.90052MR2206957
  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. (2007) Zbl1274.05235MR2357366
  3. Aouchiche, M., Hansen, P., Two Laplacians for the distance matrix of a graph, Linear Algebra Appl. 439 (2013), 21-33. (2013) Zbl1282.05086MR3045220
  4. G. A. Baker, Jr., 10.1063/1.1704911, J. Math. Phys. 7 (1966), 2238-2242. (1966) Zbl0203.27401DOI10.1063/1.1704911
  5. Brouwer, A. E., Haemers, W. H., Spectra of Graphs, Universitext Springer, Berlin (2012). (2012) Zbl1231.05001MR2882891
  6. Caporossi, G., Hansen, P., 10.1016/S0012-365X(99)00206-X, Discrete Math. 212 (2000), 29-44 (J. Harant et al., eds.). (2000) Zbl0947.90130MR1748671DOI10.1016/S0012-365X(99)00206-X
  7. Collatz, L., Sinogowitz, U., 10.1007/BF02941924, Abh. Math. Semin. Univ. Hamb. 21 German (1957), 63-77. (1957) Zbl0077.36704MR0087952DOI10.1007/BF02941924
  8. Cvetković, D. M., Graphs and their spectra, Publ. Fac. Electrotech. Univ. Belgrade, Ser. Math. Phys. 354-356 (1971), 1-50. (1971) Zbl0238.05102MR0299508
  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). (1988) Zbl0634.05054MR0926481
  10. Cvetković, D. M., Doob, M., Sachs, H., Spectra of Graphs. Theory and Applications, J. A. Barth Verlag, Leipzig (1995). (1995) Zbl0824.05046MR1324340
  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). (2010) Zbl1211.05002MR2571608
  12. Fiedler, M., Algebraic connectivity of graphs, Czech. Math. J. 23 (1973), 298-305. (1973) Zbl0265.05119MR0318007
  13. Fujii, H., Katsuda, A., 10.1016/S0012-365X(99)00133-8, Discrete Math. 207 (1999), 33-52. (1999) Zbl1131.05309MR1710481DOI10.1016/S0012-365X(99)00133-8
  14. Günthard, H. H., Primas, H., 10.1002/hlca.19560390623, Helv. Chim. Acta 39 (1956), 1645-1653 German. (1956) DOI10.1002/hlca.19560390623
  15. Haemers, W. H., Spence, E., 10.1016/S0195-6698(03)00100-8, Eur. J. Comb. 25 (2004), 199-211. (2004) Zbl1033.05070MR2070541DOI10.1016/S0195-6698(03)00100-8
  16. Halbeisen, L., Hungerbühler, N., 10.1002/(SICI)1097-0118(199907)31:3<255::AID-JGT7>3.0.CO;2-6, J. Graph Theory 31 (1999), 255-265. (1999) Zbl0932.05053MR1688950DOI10.1002/(SICI)1097-0118(199907)31:3<255::AID-JGT7>3.0.CO;2-6
  17. Holton, D. A., Sheehan, J., The Petersen Graph, Australian Mathematical Society Lecture Series 7 Cambridge University Press, Cambridge (1993). (1993) Zbl0781.05001MR1232658
  18. Marcus, M., Minc, H., A Survey of Matrix Theory and Matrix Inequalities. Reprint of the 1969 edition, Dover Publications, New York (1992). (1992) MR1215484
  19. McKay, B. D., On the spectral characterisation of trees, Ars Comb. 3 (1977), 219-232. (1977) Zbl0404.05045MR0543669
  20. Merris, R., 10.1080/03081089708818525, Linear Multilinear Algebra 43 (1997), 201-205. (1997) Zbl0887.05036MR1613203DOI10.1080/03081089708818525
  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. (1994) Zbl0802.05053MR1275613
  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. (2004) Zbl1161.05334MR2125091
  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. (1973) MR0384582
  24. Tan, J., On isospectral graphs, Interdiscip. Inf. Sci. 4 (1998), 117-124. (1998) Zbl0926.05027MR1664212
  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. (2003) MR2022290

NotesEmbed ?

top

You must be logged in to post comments.