Geodesic
Some graphs determined by their (signless) Laplacian spectra
Czechoslovak Mathematical Journal, Tome 62 (2012) no. 4, pp. 1117-1134 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Let $W_{n}=K_{1}\vee C_{n-1}$ be the wheel graph on $n$ vertices, and let $S(n,c,k)$ be the graph on $n$ vertices obtained by attaching $n-2c-2k-1$ pendant edges together with $k$ hanging paths of length two at vertex $v_{0}$, where $v_{0}$ is the unique common vertex of $c$ triangles. In this paper we show that $S(n,c,k)$ ($c\geq 1$, $k\geq 1$) and $W_{n}$ are determined by their signless Laplacian spectra, respectively. Moreover, we also prove that $S(n,c,k)$ and its complement graph are determined by their Laplacian spectra, respectively, for $c\geq 0$ and $k\geq 1$.
Let $W_{n}=K_{1}\vee C_{n-1}$ be the wheel graph on $n$ vertices, and let $S(n,c,k)$ be the graph on $n$ vertices obtained by attaching $n-2c-2k-1$ pendant edges together with $k$ hanging paths of length two at vertex $v_{0}$, where $v_{0}$ is the unique common vertex of $c$ triangles. In this paper we show that $S(n,c,k)$ ($c\geq 1$, $k\geq 1$) and $W_{n}$ are determined by their signless Laplacian spectra, respectively. Moreover, we also prove that $S(n,c,k)$ and its complement graph are determined by their Laplacian spectra, respectively, for $c\geq 0$ and $k\geq 1$.
DOI : 10.1007/s10587-012-0067-9
Classification : 05C50, 15A18
Keywords: Laplacian spectrum; signless Laplacian spectrum; complement graph 
@article{10_1007_s10587_012_0067_9,
     author = {Liu, Muhuo},
     title = {Some graphs determined by their (signless) {Laplacian} spectra},
     journal = {Czechoslovak Mathematical Journal},
     pages = {1117--1134},
     year = {2012},
     volume = {62},
     number = {4},
     doi = {10.1007/s10587-012-0067-9},
     mrnumber = {3010260},
     zbl = {1274.05299},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-012-0067-9/}
}
TY  - JOUR
AU  - Liu, Muhuo
TI  - Some graphs determined by their (signless) Laplacian spectra
JO  - Czechoslovak Mathematical Journal
PY  - 2012
SP  - 1117
EP  - 1134
VL  - 62
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-012-0067-9/
DO  - 10.1007/s10587-012-0067-9
LA  - en
ID  - 10_1007_s10587_012_0067_9
ER  - 
%0 Journal Article
%A Liu, Muhuo
%T Some graphs determined by their (signless) Laplacian spectra
%J Czechoslovak Mathematical Journal
%D 2012
%P 1117-1134
%V 62
%N 4
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-012-0067-9/
%R 10.1007/s10587-012-0067-9
%G en
%F 10_1007_s10587_012_0067_9
Liu, Muhuo. Some graphs determined by their (signless) Laplacian spectra. Czechoslovak Mathematical Journal, Tome 62 (2012) no. 4, pp. 1117-1134. doi: 10.1007/s10587-012-0067-9

[1] Borovićanin, B., Petrović, M.: On the index of cactuses with $n$ vertices. Publ. Inst. Math., Nouv. Sér. 79(93) (2006), 13-18. | DOI | MR

[2] Čvetković, D., Rowlinson, P., Simić, S. K.: Signless Laplacians of finite graphs. Linear Algebra Appl. 423 (2007), 155-171. | DOI | MR | Zbl

[3] Cvetković, D., Simić, S. K.: Towards a spectral theory of graphs based on the signless Laplacian II. Linear Algebra Appl. 432 (2010), 2257-2272. | MR | Zbl

[4] Dam, E. R. van, Haemers, W. H.: Which graphs are determined by their spectrum?. Linear Algebra Appl. 373 (2003), 241-272. | MR

[5] Das, K. Ch.: The Laplacian spectrum of a graph. Comput. Math. Appl. 48 (2004), 715-724. | DOI | MR | Zbl

[6] Das, K. Ch.: On conjectures involving second largest signless Laplacian eigenvalue of graphs. Linear Algebra Appl. 432 (2010), 3018-3029. | DOI | MR | Zbl

[7] Doob, M., Haemers, W. H.: The complement of the path is determined by its spectrum. Linear Algebra Appl. 356 (2002), 57-65. | MR | Zbl

[8] Du, Z. B., Liu, Z. Z.: On the Estrada and Laplacian Estrada indices of graphs. Linear Algebra Appl. 435 (2011), 2065-2076. | DOI | MR | Zbl

[9] Du, Z. B., Zhou, B.: Minimum on Wiener indices of trees and unicyclic graphs of the given matching number. MATCH Commun. Math. Comput. Chem. 63 (2010), 101-112. | MR

[10] Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23(98) (1973), 298-305. | MR | Zbl

[11] Guo, J. M.: The effect on the Laplacian spectral radius of a graph by adding or grafting edges. Linear Algebra Appl. 413 (2006), 59-71. | MR | Zbl

[12] Haemers, W. H.: Interlacing eigenvalues and graphs. Linear Algebra Appl. 226-228 (1995), 593-616. | MR | Zbl

[13] Heuvel, J. van den: Hamilton cycles and eigenvalues of graphs. Linear Algebra Appl. 226-228 (1995), 723-730. | MR

[14] Horn, R. A., Johnson, C. R.: Matrix Analysis. Cambridge University Press XIII, Cambridge (1985). | MR | Zbl

[15] Ilić, A.: Trees with minimal Laplacian coefficients. Comput. Math. Appl. 59 (2010), 2776-2783. | DOI | MR | Zbl

[16] Li, J. S., Pan, Y. L.: A note on the second largest eigenvalue of the Laplacian matrix of a graph. Linear Multilinear Algebra 48 (2000), 117-121. | DOI | MR | Zbl

[17] Li, S. C., Zhang, M. J.: On the signless Laplacian index of cacti with a given number of pendant vertices. Linear Algebra Appl. 436 (2012), 4400-4411. | MR | Zbl

[18] Liu, B. L.: Combinatorial Matrix Theory. Science Press, Beijing (2005), Chinese.

[19] Liu, H. Q., Lu, M.: A unified approach to extremal cacti for different indices. MATCH Commun. Math. Comput. Chem. 58 (2007), 183-194. | MR | Zbl

[20] Liu, M. H., Tan, X. Z., Liu, B. L.: The (signless) Laplacian spectral radius of unicyclic and bicyclic graphs with $n$ vertices and $k$ pendant vertices. Czech. Math. J. 60 (2010), 849-867. | DOI | MR | Zbl

[21] Liu, M. H., Liu, B. L., Wei, F. Y.: Graphs determined by their (signless) Laplacian spectra. Electron. J. Linear Algebra 22 (2011), 112-124. | MR | Zbl

[22] Liu, X. G., Zhang, Y. P., Gui, X. Q.: The multi-fan graphs are determined by their Laplacian spectra. Discrete Math. 308 (2008), 4267-4271. | DOI | MR | Zbl

[23] Lotker, Z.: Note on deleting a vertex and weak interlacing of the Laplacian spectrum. Electron. J. Linear Algebra. 16 (2007), 68-72. | DOI | MR | Zbl

[24] Merris, R.: Laplacian matrices of graphs: A survey. Linear Algebra Appl. 197-198 (1994), 143-176. | MR | Zbl

[25] Pan, Y. L.: Sharp upper bounds for the Laplacian graph eigenvalues. Linear Algebra Appl. 355 (2002), 287-295. | MR | Zbl

[26] Radosavljević, Z., sajski, M. Ra\u: A class of reflexive cactuses with four cycles. Publ. Elektroteh. Fak., Univ. Beogr., Ser. Mat. 14 (2003), 64-85. | MR

[27] Shen, X. L., Hou, Y. P.: A class of unicyclic graphs determined by their Laplacian spectrum. Electron. J. Linear Algebra. 23 (2012), 375-386. | MR

[28] Yu, G. H., Feng, L. H., Ilić, A.: The hyper-Wiener index of trees with given parameters. Ars Comb. 96 (2010), 395-404. | MR | Zbl

[29] Zhang, X. L., Zhang, H. P.: Some graphs determined by their spectra. Linear Algebra Appl. 431 (2009), 1443-1454. | DOI | MR | Zbl

[30] Zhang, Y. P., Liu, X. G., Yong, X. R.: Which wheel graphs are determined by their Laplacian spectra?. Comput Math. Appl. 58 (2009), 1887-1890. | DOI | MR | Zbl

[31] Zhang, Y. P., Liu, X. G., Zhang, B. Y., Yong, X. R.: The lollipop graph is determined by its $Q$-spectrum. Discrete Math. 309 (2009), 3364-3369. | DOI | MR | Zbl

Cité par Sources :