Some graphs determined by their (signless) Laplacian spectra

Muhuo Liu

Czechoslovak Mathematical Journal (2012)

  • Volume: 62, Issue: 4, page 1117-1134
  • ISSN: 0011-4642

Abstract

top
Let W n = K 1 ∨ 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 - 2 c - 2 k - 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 ≥ 1 , k ≥ 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 ≥ 0 and k ≥ 1 .

How to cite

top

Liu, Muhuo. "Some graphs determined by their (signless) Laplacian spectra." Czechoslovak Mathematical Journal 62.4 (2012): 1117-1134. <http://eudml.org/doc/246215>.

@article{Liu2012,
abstract = {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\ge 1$, $k\ge 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\ge 0$ and $k\ge 1$.},
author = {Liu, Muhuo},
journal = {Czechoslovak Mathematical Journal},
keywords = {Laplacian spectrum; signless Laplacian spectrum; complement graph; Laplacian spectrum; signless Laplacian spectrum; complement graph; adjacency matrix; wheels; maximal spectral radius},
language = {eng},
number = {4},
pages = {1117-1134},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Some graphs determined by their (signless) Laplacian spectra},
url = {http://eudml.org/doc/246215},
volume = {62},
year = {2012},
}

TY - JOUR
AU - Liu, Muhuo
TI - Some graphs determined by their (signless) Laplacian spectra
JO - Czechoslovak Mathematical Journal
PY - 2012
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 62
IS - 4
SP - 1117
EP - 1134
AB - 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\ge 1$, $k\ge 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\ge 0$ and $k\ge 1$.
LA - eng
KW - Laplacian spectrum; signless Laplacian spectrum; complement graph; Laplacian spectrum; signless Laplacian spectrum; complement graph; adjacency matrix; wheels; maximal spectral radius
UR - http://eudml.org/doc/246215
ER -

References

top
  1. Borovićanin, B., Petrović, M., 10.2298/PIM0693013B, Publ. Inst. Math., Nouv. Sér. 79(93) (2006), 13-18. (2006) MR2275334DOI10.2298/PIM0693013B
  2. Čvetković, D., Rowlinson, P., Simić, S. K., 10.1016/j.laa.2007.01.009, Linear Algebra Appl. 423 (2007), 155-171. (2007) Zbl1113.05061MR2312332DOI10.1016/j.laa.2007.01.009
  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. (2010) Zbl1218.05089MR2599858
  4. Dam, E. R. van, Haemers, W. H., Which graphs are determined by their spectrum?, Linear Algebra Appl. 373 (2003), 241-272. (2003) MR2022290
  5. Das, K. Ch., 10.1016/j.camwa.2004.05.005, Comput. Math. Appl. 48 (2004), 715-724. (2004) Zbl1058.05048MR2105246DOI10.1016/j.camwa.2004.05.005
  6. Das, K. Ch., 10.1016/j.laa.2010.01.005, Linear Algebra Appl. 432 (2010), 3018-3029. (2010) Zbl1195.05040MR2639266DOI10.1016/j.laa.2010.01.005
  7. Doob, M., Haemers, W. H., The complement of the path is determined by its spectrum, Linear Algebra Appl. 356 (2002), 57-65. (2002) Zbl1015.05047MR1944676
  8. Du, Z. B., Liu, Z. Z., 10.1016/j.laa.2011.03.057, Linear Algebra Appl. 435 (2011), 2065-2076. (2011) Zbl1221.05211MR2810647DOI10.1016/j.laa.2011.03.057
  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. (2010) MR2582967
  10. Fiedler, M., Algebraic connectivity of graphs, Czech. Math. J. 23(98) (1973), 298-305. (1973) Zbl0265.05119MR0318007
  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. (2006) Zbl1082.05059MR2202092
  12. Haemers, W. H., Interlacing eigenvalues and graphs, Linear Algebra Appl. 226-228 (1995), 593-616. (1995) Zbl0831.05044MR1344588
  13. Heuvel, J. van den, Hamilton cycles and eigenvalues of graphs, Linear Algebra Appl. 226-228 (1995), 723-730. (1995) MR1344594
  14. Horn, R. A., Johnson, C. R., Matrix Analysis, Cambridge University Press XIII, Cambridge (1985). (1985) Zbl0576.15001MR0832183
  15. Ilić, A., 10.1016/j.camwa.2010.01.047, Comput. Math. Appl. 59 (2010), 2776-2783. (2010) Zbl1193.05060MR2607982DOI10.1016/j.camwa.2010.01.047
  16. Li, J. S., Pan, Y. L., 10.1080/03081080008818663, Linear Multilinear Algebra 48 (2000), 117-121. (2000) Zbl0979.15016MR1813439DOI10.1080/03081080008818663
  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. (2012) Zbl1241.05082MR2917417
  18. Liu, B. L., Combinatorial Matrix Theory, Science Press, Beijing (2005), Chinese. (2005) 
  19. Liu, H. Q., Lu, M., A unified approach to extremal cacti for different indices, MATCH Commun. Math. Comput. Chem. 58 (2007), 183-194. (2007) Zbl1164.05043MR2335488
  20. Liu, M. H., Tan, X. Z., Liu, B. L., 10.1007/s10587-010-0053-z, Czech. Math. J. 60 (2010), 849-867. (2010) Zbl1224.05311MR2672419DOI10.1007/s10587-010-0053-z
  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. (2011) Zbl1227.05185MR2781040
  22. Liu, X. G., Zhang, Y. P., Gui, X. Q., 10.1016/j.disc.2007.08.002, Discrete Math. 308 (2008), 4267-4271. (2008) Zbl1225.05172MR2427757DOI10.1016/j.disc.2007.08.002
  23. Lotker, Z., 10.13001/1081-3810.1183, Electron. J. Linear Algebra. 16 (2007), 68-72. (2007) Zbl1142.05342MR2285833DOI10.13001/1081-3810.1183
  24. Merris, R., Laplacian matrices of graphs: A survey, Linear Algebra Appl. 197-198 (1994), 143-176. (1994) Zbl0802.05053MR1275613
  25. Pan, Y. L., Sharp upper bounds for the Laplacian graph eigenvalues, Linear Algebra Appl. 355 (2002), 287-295. (2002) Zbl1015.05055MR1930150
  26. Radosavljević, Z., A class of reflexive cactuses with four cycles, Publ. Elektroteh. Fak., Univ. Beogr., Ser. Mat. 14 (2003), 64-85. (2003) MR2076310
  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. (2012) MR2928565
  28. Yu, G. H., Feng, L. H., Ilić, A., The hyper-Wiener index of trees with given parameters, Ars Comb. 96 (2010), 395-404. (2010) Zbl1247.92068MR2666825
  29. Zhang, X. L., Zhang, H. P., 10.1016/j.laa.2009.05.018, Linear Algebra Appl. 431 (2009), 1443-1454. (2009) Zbl1169.05354MR2555048DOI10.1016/j.laa.2009.05.018
  30. Zhang, Y. P., Liu, X. G., Yong, X. R., 10.1016/j.camwa.2009.07.028, Comput Math. Appl. 58 (2009), 1887-1890. (2009) Zbl1189.05111MR2557510DOI10.1016/j.camwa.2009.07.028
  31. Zhang, Y. P., Liu, X. G., Zhang, B. Y., Yong, X. R., 10.1016/j.disc.2008.09.052, Discrete Math. 309 (2009), 3364-3369. (2009) Zbl1182.05084MR2526754DOI10.1016/j.disc.2008.09.052

NotesEmbed ?

top

You must be logged in to post comments.