Revista de la
Unión Matemática Argentina
Distance Laplacian eigenvalues of graphs, and chromatic and independence number
Shariefuddin Pirzada and Saleem Khan

Volume 67, no. 1 (2024), pp. 145–159    

Published online: April 16, 2024

https://doi.org/10.33044/revuma.3235

Download PDF

Abstract

Given an interval $I$, let $m_{D^{L} (G)} I$ (or simply $m_{D^{L}} I$) be the number of distance Laplacian eigenvalues of a graph $G$ which lie in $I$. For a prescribed interval $I$, we give the bounds for $m_{D^{L} }I$ in terms of the independence number $\alpha(G)$, the chromatic number $\chi$, the number of pendant vertices $p$, the number of components in the complement graph $C_{\overline{G}}$ and the diameter $d$ of $G$. In particular, we prove that $m_{D^{L}(G) }[n,n+2)\leq \chi-1$, $m_{D^{L}(G)}[n,n+\alpha(G))\leq n-\alpha(G)$, $m_{D^{L}(G) }[n,n+p)\leq n-p$ and discuss the cases where the bounds are best possible. In addition, we characterize graphs of diameter $d\leq 2$ which satisfy $m_{D^{L}(G) } (2n-1,2n )= \alpha(G)-1=\frac{n}{2}-1$. We also propose some problems of interest.

References

  1. M. Ahanjideh, S. Akbari, M. H. Fakharan, and V. Trevisan, Laplacian eigenvalue distribution and graph parameters, Linear Algebra Appl. 632 (2022), 1–14.  DOI  MR  Zbl
  2. M. Aouchiche and P. Hansen, Two Laplacians for the distance matrix of a graph, Linear Algebra Appl. 439 no. 1 (2013), 21–33.  DOI  MR  Zbl
  3. M. Aouchiche and P. Hansen, Some properties of the distance Laplacian eigenvalues of a graph, Czechoslovak Math. J. 64(139) no. 3 (2014), 751–761.  DOI  MR  Zbl
  4. M. Aouchiche and P. Hansen, Distance Laplacian eigenvalues and chromatic number in graphs, Filomat 31 no. 9 (2017), 2545–2555.  DOI  MR  Zbl
  5. D. M. Cardoso, D. P. Jacobs, and V. Trevisan, Laplacian distribution and domination, Graphs Combin. 33 no. 5 (2017), 1283–1295.  DOI  MR  Zbl
  6. D. Cvetković, P. Rowlinson, and S. Simić, An introduction to the theory of graph spectra, London Mathematical Society Student Texts 75, Cambridge: Cambridge University Press, New York, 2010.  DOI  MR  Zbl
  7. J. F. Fink, M. S. Jacobson, L. F. Kinch, and J. Roberts, On graphs having domination number half their order, Period. Math. Hungar. 16 no. 4 (1985), 287–293.  DOI  MR  Zbl
  8. R. Grone, R. Merris, and V. S. Sunder, The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl. 11 no. 2 (1990), 218–238.  DOI  MR  Zbl
  9. J. M. Guo and T. S. Wang, A relation between the matching number and Laplacian spectrum of a graph, Linear Algebra Appl. 325 no. 1-3 (2001), 71–74.  DOI  MR  Zbl
  10. S. T. Hedetniemi, D. P. Jacobs, and V. Trevisan, Domination number and Laplacian eigenvalue distribution, European J. Combin. 53 (2016), 66–71.  DOI  MR  Zbl
  11. Q. Liu, The Laplacian spectrum of corona of two graphs, Kragujevac J. Math. 38 no. 1 (2014), 163–170.  DOI  MR
  12. M. Marcus and H. Minc, A survey of matrix theory and matrix inequalities, Dover, New York, 1992.  MR
  13. R. Merris, The number of eigenvalues greater than two in the Laplacian spectrum of a graph, Portugal. Math. 48 no. 3 (1991), 345–349.  MR  Zbl Available at http://eudml.org/doc/115760.
  14. S. Pirzada, An introduction to graph theory, Universities Press, Hyderabad, India, 2012.
  15. S. Pirzada and S. Khan, On distance Laplacian spectral radius and chromatic number of graphs, Linear Algebra Appl. 625 (2021), 44–54.  DOI  MR  Zbl
  16. S. Pirzada and S. Khan, On the sum of distance Laplacian eigenvalues of graphs, Tamkang J. Math. 54 no. 1 (2023), 83–91.  DOI  MR  Zbl