Reflexive line graphs of trees. (English) Zbl 1409.05173
Summary: 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.
MSC:
| 05C76 | Graph operations (line graphs, products, etc.) |
| 05C05 | Trees |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
Keywords:
line graph; subdivision graph; adjacency matrix; second largest eigenvalue; reflexive graph; Salem graphReferences:
| [1] | Cao, D., Yuan, H.: Graphs characterized by the second eigenvalue. J. Graph Theory 17(3), 325-331 (1993) · Zbl 0786.05055 · doi:10.1002/jgt.3190170307 |
| [2] | Cvetković, D., Rowlinson, P., Simić, S.: Spectral Generalizations of Line Graphs: On Graphs with Least Eigenvalue-2. Cambridge University Press, Cambridge (2004) · Zbl 1061.05057 · doi:10.1017/CBO9780511751752 |
| [3] | Cvetković, D., Rowlinson, P., Simić, S.: An Introduction to the Theory of Graph Spectra. Cambridge University Press, Cambridge (2009) · doi:10.1017/CBO9780511801518 |
| [4] | Cvetković, D., Simić, S.: On graphs whose second largest eigenvalue does not exceed \[(\sqrt{5} - 1)/2\](\sqrt{5}-1)/2. Discret. Math. 138, 213-227 (1995) · Zbl 0842.05059 · doi:10.1016/0012-365X(94)00204-V |
| [5] | Gumbrell, L.: On spectral constructions for Salem graphs. Doctoral Thesis, Royal Holloway, University of London (2013) · Zbl 1282.05116 |
| [6] | Gumbrell, L., McKee, J.: A classification of all \[11\]-Salem graphs. LMS J. Comput. Math 17(1), 582-594 (2014) · Zbl 1346.05164 · doi:10.1112/S1461157014000060 |
| [7] | Maxwell, G.: Hyperbolic trees. J. Algebra 54, 46-49 (1978) · Zbl 0389.05031 · doi:10.1016/0021-8693(78)90021-2 |
| [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 · Zbl 0931.11041 |
| [9] | McKee, J., Smyth, C.: Salem numbers, Pisot numbers, Mahler measure, and graphs. Exp. Math. 14(2), 211-229 (2005) · Zbl 1082.11066 · doi:10.1080/10586458.2005.10128915 |
| [10] | Neumaier, A.: The second largest eigenvalue of trees. Linear Algebra Appl. 46, 2-25 (1982) · Zbl 0495.05044 · doi:10.1016/0024-3795(82)90022-2 |
| [11] | Neumaier, A., Seidel, J.J.: Discrete hyperbolic geometry. Combinatorica 3(2), 219-237 (1983) · Zbl 0523.51016 · doi:10.1007/BF02579296 |
| [12] | Petrović, M.: On graphs whose second largest eigenvalue does not exceed \[\sqrt{2}-1\sqrt{2}-1\], Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. no. 735 - no. 762, pp. 142-147 (1982) · Zbl 0842.05059 |
| [13] | Petrović, M., Milekić, B.: On the second largest eigenvalue of line graphs. J. Graph Theory 27(2), 61-66 (1998) · Zbl 0892.05031 · doi:10.1002/(SICI)1097-0118(199802)27:2<61::AID-JGT1>3.0.CO;2-D |
| [14] | Petrović, M., Milekić, B.: On the second largest eigenvalue of generalized line graphs. Publ. Inst. Math. (Beograd) 68(82), 37-45 (2000) · Zbl 0968.05054 |
| [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) · Zbl 1222.05176 · doi:10.1016/j.laa.2011.04.023 |
| [16] | Radosavljević, Z.: On unicyclic reflexive graphs. Appl. Anal. Discret. Math. 1, 228-240 (2007) · Zbl 1199.05238 · doi:10.2298/AADM0701228R |
| [17] | Radosavljević, Z., Simić, S.: Which bicyclic graphs are reflexive? Univ. Beograd Publ. Elektrotehn. Fak. Ser. Mat. 7, 90-104 (1996) · Zbl 0941.05044 |
| [18] | Simić, S.: Some notes on graphs whose second largest eigenvalue is less than \[(\sqrt{5} - 1)/2\](\sqrt{5}-1)/2. Linear Multilinear Algebra 39, 59-71 (1995) · Zbl 0832.05077 · doi:10.1080/03081089508818380 |
| [19] | Simić, S.K.: Arbitrarily large graphs whose second largest eigenvalue is less than \[(\sqrt{5}-1)/2\](\sqrt{5}-1)/2. Rend. Semin. Mat. Messina Ser. II 8, 1-25 (2002) · Zbl 1043.05079 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
