Revista de la
Unión Matemática Argentina
Monster graphs are determined by their Laplacian spectra
Ali Zeydi Abdian, Ali Reza Ashrafi, Lowell W. Beineke, Mohammad Reza Oboudi, and Gholam Hossein Fath-Tabar
Volume 63, no. 2 (2022), pp. 413–424    

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

Download PDF

Abstract

A graph $G$ is determined by its Laplacian spectrum (DLS) if every graph with the same Laplacian spectrum is isomorphic to $G$. A multi-fan graph is a graph of the form $(P_{n_1}\cup P_{n_2}\cup \cdots \cup P_{n_k})\bigtriangledown K_1$, where $K_1$ denotes the complete graph of size 1, $P_{n_1}\cup P_{n_2}\cup \cdots \cup P_{n_k}$ is the disjoint union of paths $P_{n_i}$, $n_i\geq 1$ and $1 \leq i \leq k$; and a starlike tree is a tree with exactly one vertex of degree greater than 2. If a multi-fan graph and a starlike tree are joined by identifying their vertices of degree more than 2, then the resulting graph is called a monster graph. In some earlier works, it was shown that all multi-fan and path-friendship graphs are DLS. The aim of this paper is to generalize these facts by proving that all monster graphs are DLS.

References

  1. W. N. Anderson, Jr. and T. D. Morley, Eigenvalues of the Laplacian of a graph, Linear and Multilinear Algebra 18 (1985), no. 2, 141–145. MR 0817657.
  2. D. Cvetković, P. Rowlinson and S. Simić, An Introduction to the Theory of Graph Spectra, London Mathematical Society Student Texts, 75, Cambridge University Press, Cambridge, 2010. MR 2571608.
  3. K. Ch. Das, The Laplacian spectrum of a graph, Comput. Math. Appl. 48 (2004), no. 5-6, 715–724. MR 2105246.
  4. K. Ch. Das, Proof of conjectures on adjacency eigenvalues of graphs, Discrete Math. 313 (2013), no. 1, 19–25. MR 3016969.
  5. L. Feng and G. Yu, No starlike trees are Laplacian cospectral, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 18 (2007), 46–51. MR 2311791.
  6. R. Grone and R. Merris, The Laplacian spectrum of a graph. II, SIAM J. Discrete Math. 7 (1994), no. 2, 221–229. MR 1271994.
  7. J.-M. Guo, The effect on the Laplacian spectral radius of a graph by adding or grafting edges, Linear Algebra Appl. 413 (2006), no. 1, 59–71. MR 2202092.
  8. F. Liu and Q. Huang, Laplacian spectral characterization of 3-rose graphs, Linear Algebra Appl. 439 (2013), no. 10, 2914–2920. MR 3116401.
  9. X. Liu, Y. Zhang and X. Gui, The multi-fan graphs are determined by their Laplacian spectra, Discrete Math. 308 (2008), no. 18, 4267–4271. MR 2427757.
  10. M. Liu, Y. Zhu, H. Shan and K. Ch. Das, The spectral characterization of butterfly-like graphs, Linear Algebra Appl. 513 (2017), 55–68. MR 3573788.
  11. Z. Lotker, Note on deleting a vertex and weak interlacing of the Laplacian spectrum, Electron. J. Linear Algebra 16 (2007), 68–72. MR 2285833.
  12. R. Merris, A note on Laplacian graph eigenvalues, Linear Algebra Appl. 285 (1998), no. 1-3, 33–35. MR 1653479.
  13. M. R. Oboudi, A. Z. Abdian, A. R. Ashrafi and L. W. Beineke, Laplacian spectral determination of path-friendship graphs, AKCE Int. J. Graphs Comb. 18 (2021), no. 1, 33–38. MR 4277577.
  14. C. S. Oliveira, N. M. Maia de Abreu and S. Jurkiewicz, The characteristic polynomial of the Laplacian of graphs in $(a,b)$-linear classes, Linear Algebra Appl. 356 (2002), 113–121. MR 1944681.
  15. G. R. Omidi, On a signless Laplacian spectral characterization of $T$-shape trees, Linear Algebra Appl. 431 (2009), no. 9, 1607–1615. MR 2555062.
  16. E. R. van Dam and W. H. Haemers, Which graphs are determined by their spectrum?, Linear Algebra Appl. 373 (2003), 241–272. MR 2022290.
  17. F. Wen, Q. Huang, X. Huang and F. Liu, The spectral characterization of wind-wheel graphs, Indian J. Pure Appl. Math. 46 (2015), no. 5, 613–631. MR 3407192.