Monster graphs are determined by their Laplacian spectra

Authors

  • Ali Zeydi Abdian Department of Mathematical Sciences, College of Science, Lorestan University, Lorestan, Khoramabad, Iran
  • Ali Reza Ashrafi Department of Pure Mathematics, Faculty of Mathematical Sciences, University of Kashan, Kashan 87317-53153, Iran
  • Lowell W. Beineke Department of Mathematical Sciences, Purdue University Fort Wayne, Fort Wayne, Indiana 46805, USA
  • Mohammad Reza Oboudi Department of Mathematics, College of Sciences, Shiraz University, Shiraz 71457-44776, Iran
  • Gholam Hossein Fath-Tabar Department of Pure Mathematics, Faculty of Mathematical Sciences, University of Kashan, Kashan 87317–53153, Iran

DOI:

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

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.

Downloads

Download data is not yet available.

References

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.

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.

K. Ch. Das, The Laplacian spectrum of a graph, Comput. Math. Appl. 48 (2004), no. 5-6, 715–724. MR 2105246.

K. Ch. Das, Proof of conjectures on adjacency eigenvalues of graphs, Discrete Math. 313 (2013), no. 1, 19–25. MR 3016969.

L. Feng and G. Yu, No starlike trees are Laplacian cospectral, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 18 (2007), 46–51. MR 2311791.

R. Grone and R. Merris, The Laplacian spectrum of a graph. II, SIAM J. Discrete Math. 7 (1994), no. 2, 221–229. MR 1271994.

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.

F. Liu and Q. Huang, Laplacian spectral characterization of 3-rose graphs, Linear Algebra Appl. 439 (2013), no. 10, 2914–2920. MR 3116401.

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.

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.

Z. Lotker, Note on deleting a vertex and weak interlacing of the Laplacian spectrum, Electron. J. Linear Algebra 16 (2007), 68–72. MR 2285833.

R. Merris, A note on Laplacian graph eigenvalues, Linear Algebra Appl. 285 (1998), no. 1-3, 33–35. MR 1653479.

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.

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.

G. R. Omidi, On a signless Laplacian spectral characterization of $T$-shape trees, Linear Algebra Appl. 431 (2009), no. 9, 1607–1615. MR 2555062.

E. R. van Dam and W. H. Haemers, Which graphs are determined by their spectrum?, Linear Algebra Appl. 373 (2003), 241–272. MR 2022290.

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.

Downloads

Published

2022-11-03