| Title:
|
Some graphs determined by their (signless) Laplacian spectra (English) |
| Author:
|
Liu, Muhuo |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
62 |
| Issue:
|
4 |
| Year:
|
2012 |
| Pages:
|
1117-1134 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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$. (English) |
| Keyword:
|
Laplacian spectrum |
| Keyword:
|
signless Laplacian spectrum |
| Keyword:
|
complement graph |
| MSC:
|
05C50 |
| MSC:
|
15A18 |
| idZBL:
|
Zbl 1274.05299 |
| idMR:
|
MR3010260 |
| DOI:
|
10.1007/s10587-012-0067-9 |
| . |
| Date available:
|
2012-11-10T21:49:56Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143048 |
| . |
| Reference:
|
[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. MR 2275334, 10.2298/PIM0693013B |
| Reference:
|
[2] Čvetković, D., Rowlinson, P., Simić, S. K.: Signless Laplacians of finite graphs.Linear Algebra Appl. 423 (2007), 155-171. Zbl 1113.05061, MR 2312332, 10.1016/j.laa.2007.01.009 |
| Reference:
|
[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. Zbl 1218.05089, MR 2599858 |
| Reference:
|
[4] Dam, E. R. van, Haemers, W. H.: Which graphs are determined by their spectrum?.Linear Algebra Appl. 373 (2003), 241-272. MR 2022290 |
| Reference:
|
[5] Das, K. Ch.: The Laplacian spectrum of a graph.Comput. Math. Appl. 48 (2004), 715-724. Zbl 1058.05048, MR 2105246, 10.1016/j.camwa.2004.05.005 |
| Reference:
|
[6] Das, K. Ch.: On conjectures involving second largest signless Laplacian eigenvalue of graphs.Linear Algebra Appl. 432 (2010), 3018-3029. Zbl 1195.05040, MR 2639266, 10.1016/j.laa.2010.01.005 |
| Reference:
|
[7] Doob, M., Haemers, W. H.: The complement of the path is determined by its spectrum.Linear Algebra Appl. 356 (2002), 57-65. Zbl 1015.05047, MR 1944676 |
| Reference:
|
[8] Du, Z. B., Liu, Z. Z.: On the Estrada and Laplacian Estrada indices of graphs.Linear Algebra Appl. 435 (2011), 2065-2076. Zbl 1221.05211, MR 2810647, 10.1016/j.laa.2011.03.057 |
| Reference:
|
[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 2582967 |
| Reference:
|
[10] Fiedler, M.: Algebraic connectivity of graphs.Czech. Math. J. 23(98) (1973), 298-305. Zbl 0265.05119, MR 0318007 |
| Reference:
|
[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. Zbl 1082.05059, MR 2202092 |
| Reference:
|
[12] Haemers, W. H.: Interlacing eigenvalues and graphs.Linear Algebra Appl. 226-228 (1995), 593-616. Zbl 0831.05044, MR 1344588 |
| Reference:
|
[13] Heuvel, J. van den: Hamilton cycles and eigenvalues of graphs.Linear Algebra Appl. 226-228 (1995), 723-730. MR 1344594 |
| Reference:
|
[14] Horn, R. A., Johnson, C. R.: Matrix Analysis.Cambridge University Press XIII, Cambridge (1985). Zbl 0576.15001, MR 0832183 |
| Reference:
|
[15] Ilić, A.: Trees with minimal Laplacian coefficients.Comput. Math. Appl. 59 (2010), 2776-2783. Zbl 1193.05060, MR 2607982, 10.1016/j.camwa.2010.01.047 |
| Reference:
|
[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. Zbl 0979.15016, MR 1813439, 10.1080/03081080008818663 |
| Reference:
|
[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. Zbl 1241.05082, MR 2917417 |
| Reference:
|
[18] Liu, B. L.: Combinatorial Matrix Theory.Science Press, Beijing (2005), Chinese. |
| Reference:
|
[19] Liu, H. Q., Lu, M.: A unified approach to extremal cacti for different indices.MATCH Commun. Math. Comput. Chem. 58 (2007), 183-194. Zbl 1164.05043, MR 2335488 |
| Reference:
|
[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. Zbl 1224.05311, MR 2672419, 10.1007/s10587-010-0053-z |
| Reference:
|
[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. Zbl 1227.05185, MR 2781040 |
| Reference:
|
[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. Zbl 1225.05172, MR 2427757, 10.1016/j.disc.2007.08.002 |
| Reference:
|
[23] Lotker, Z.: Note on deleting a vertex and weak interlacing of the Laplacian spectrum.Electron. J. Linear Algebra. 16 (2007), 68-72. Zbl 1142.05342, MR 2285833, 10.13001/1081-3810.1183 |
| Reference:
|
[24] Merris, R.: Laplacian matrices of graphs: A survey.Linear Algebra Appl. 197-198 (1994), 143-176. Zbl 0802.05053, MR 1275613 |
| Reference:
|
[25] Pan, Y. L.: Sharp upper bounds for the Laplacian graph eigenvalues.Linear Algebra Appl. 355 (2002), 287-295. Zbl 1015.05055, MR 1930150 |
| Reference:
|
[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 2076310 |
| Reference:
|
[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 2928565 |
| Reference:
|
[28] Yu, G. H., Feng, L. H., Ilić, A.: The hyper-Wiener index of trees with given parameters.Ars Comb. 96 (2010), 395-404. Zbl 1247.92068, MR 2666825 |
| Reference:
|
[29] Zhang, X. L., Zhang, H. P.: Some graphs determined by their spectra.Linear Algebra Appl. 431 (2009), 1443-1454. Zbl 1169.05354, MR 2555048, 10.1016/j.laa.2009.05.018 |
| Reference:
|
[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. Zbl 1189.05111, MR 2557510, 10.1016/j.camwa.2009.07.028 |
| Reference:
|
[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. Zbl 1182.05084, MR 2526754, 10.1016/j.disc.2008.09.052 |
| . |
