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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.