Monster graphs are determined by their Laplacian spectra
DOI:
https://doi.org/10.33044/revuma.1769Abstract
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
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
Issue
Section
License
Copyright (c) 2022 Ali Z. Abdian, Ali R. Ashrafi, Lowell W. Beineke, Mohammad Reza Oboudi, Gholam Hossein Fath-Tabar
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal. The Journal may retract the paper after publication if clear evidence is found that the findings are unreliable as a result of misconduct or honest error.
