Reflexive line graphs of trees

详细信息    查看全文

• 作者：Slobodan K. Simić ; Dejan Živković ; Milica Anđelić…
• 关键词：Line graph ; Subdivision graph ; Adjacency matrix ; Second largest eigenvalue ; Reflexive graph ; Salem graph ; 15A18 ; 05C50
• 刊名：Journal of Algebraic Combinatorics
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：43
• 期：2
• 页码：447-464
• 全文大小：615 KB
• 参考文献：1.Cao, D., Yuan, H.: Graphs characterized by the second eigenvalue. J. Graph Theory 17(3), 325–331 (1993)CrossRef MathSciNet MATH
  2.Cvetković, D., Rowlinson, P., Simić, S.: Spectral Generalizations of Line Graphs: On Graphs with Least Eigenvalue-2. Cambridge University Press, Cambridge (2004)CrossRef
  3.Cvetković, D., Rowlinson, P., Simić, S.: An Introduction to the Theory of Graph Spectra. Cambridge University Press, Cambridge (2009)CrossRef
  4.Cvetković, D., Simić, S.: On graphs whose second largest eigenvalue does not exceed \((\sqrt{5} - 1)/2\) . Discret. Math. 138, 213–227 (1995)CrossRef MATH
  5.Gumbrell, L.: On spectral constructions for Salem graphs. Doctoral Thesis, Royal Holloway, University of London (2013)
  6.Gumbrell, L., McKee, J.: A classification of all \(1\) -Salem graphs. LMS J. Comput. Math 17(1), 582–594 (2014)CrossRef MathSciNet
  7.Maxwell, G.: Hyperbolic trees. J. Algebra 54, 46–49 (1978)CrossRef MathSciNet MATH
  8.McKee, J., Rowlinson, P., Smyth, C.: Salem numbers and Pisot numbers from stars. In: Gyory, K., Iwaniec, H., Urbanowicz, J. (eds.) Number Theory in Progress, Proceedings of International Conference on Number Theory (Zakopane, Poland, 1997), Walter De Gruyter (Berlin, 1999) Part 1: Diophantine Problems and Polynomials, pp. 309–319
  9.McKee, J., Smyth, C.: Salem numbers, Pisot numbers, Mahler measure, and graphs. Exp. Math. 14(2), 211–229 (2005)CrossRef MathSciNet MATH
  10.Neumaier, A.: The second largest eigenvalue of trees. Linear Algebra Appl. 46, 2–25 (1982)CrossRef MathSciNet
  11.Neumaier, A., Seidel, J.J.: Discrete hyperbolic geometry. Combinatorica 3(2), 219–237 (1983)CrossRef MathSciNet MATH
  12.Petrović, M.: On graphs whose second largest eigenvalue does not exceed \(\sqrt{2}-1\) , Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. no. 735 – no. 762, pp. 142–147 (1982)
  13.Petrović, M., Milekić, B.: On the second largest eigenvalue of line graphs. J. Graph Theory 27(2), 61–66 (1998)CrossRef MathSciNet MATH
  14.Petrović, M., Milekić, B.: On the second largest eigenvalue of generalized line graphs. Publ. Inst. Math. (Beograd) 68(82), 37–45 (2000)MathSciNet
  15.Rašajski, M., Radosavljević, Z., Mihailović, B.: Maximal reflexive cactii with four cycles: the approach via Smith graphs. Linear Algebra Appl. 435, 2530–2543 (2011)CrossRef MathSciNet MATH
  16.Radosavljević, Z.: On unicyclic reflexive graphs. Appl. Anal. Discret. Math. 1, 228–240 (2007)CrossRef MATH
  17.Radosavljević, Z., Simić, S.: Which bicyclic graphs are reflexive? Univ. Beograd Publ. Elektrotehn. Fak. Ser. Mat. 7, 90–104 (1996)MathSciNet MATH
  18.Simić, S.: Some notes on graphs whose second largest eigenvalue is less than \((\sqrt{5} - 1)/2\) . Linear Multilinear Algebra 39, 59–71 (1995)CrossRef MATH
  19.Simić, S.K.: Arbitrarily large graphs whose second largest eigenvalue is less than \((\sqrt{5}-1)/2\) . Rend. Semin. Mat. Messina Ser. II 8, 1–25 (2002)
  
• 作者单位：Slobodan K. Simić (1) (2)
  Dejan Živković (3)
  Milica Anđelić (4)
  Carlos M. da Fonseca (4)
  
  1. State University of Novi Pazar, Vuka Karadžića bb, 36 300, Novi Pazar, Serbia
  2. Mathematical Institute SANU, Knez Mihailova 36, 11 001, Belgrade, Serbia
  3. Faculty of Informatics and Computing, Singidunum University, Belgrade, Serbia
  4. Department of Mathematics, Kuwait University, 13060, Safat, Kuwait
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Order, Lattices and Ordered Algebraic Structures
  Computer Science, general
  Group Theory and Generalizations
  
• 出版者：Springer U.S.
• ISSN：1572-9192

文摘

A graph is reflexive if the second largest eigenvalue of its adjacency matrix is less than or equal to 2. In this paper, we characterize trees whose line graphs are reflexive. It turns out that these trees can be of arbitrary order—they can have either a unique vertex of arbitrary degree or pendant paths of arbitrary lengths, or both. Since the reflexive line graphs are Salem graphs, we also relate some of our results to the Salem (graph) numbers. Keywords Line graph Subdivision graph Adjacency matrix Second largest eigenvalue Reflexive graph Salem graph