Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
limit point; eigenvalue of digraph (graph); double cover; subdivision digraph; line digraph
limit point; eigenvalue of digraph (graph); double cover; subdivision digraph; line digraph
Summary:
The study on limit points of eigenvalues of undirected graphs was initiated by A. J. Hoffman in 1972. Now we extend the study to digraphs. We prove: 1. Every real number is a limit point of eigenvalues of graphs. Every complex number is a limit point of eigenvalues of digraphs. 2. For a digraph $D$, the set of limit points of eigenvalues of iterated subdivision digraphs of $D$ is the unit circle in the complex plane if and only if $D$ has a directed cycle. 3. Every limit point of eigenvalues of a set $\mathcal {D}$ of digraphs (graphs) is a limit point of eigenvalues of a set $\ddot{\mathcal {D}}$ of bipartite digraphs (graphs), where $\ddot{\mathcal {D}}$ consists of the double covers of the members in $\mathcal {D}$. 4. Every limit point of eigenvalues of a set $\mathcal {D}$ of digraphs is a limit point of eigenvalues of line digraphs of the digraphs in $\mathcal {D}$. 5. If $M$ is a limit point of the largest eigenvalues of graphs, then $-M$ is a limit point of the smallest eigenvalues of graphs.
References:
[1] J. A. Bondy, U. S. R. Murty: Graph Theory with Applications. Macmilliam, London, 1976. MR 0411988
[2] D. Cao D, H. Yuan: Graphs characterized by the second eigenvalue. J. Graph Theory 17 (1993), 325–331. DOI 10.1002/jgt.3190170307 | MR 1220993
[3] D. Cao, H. Yuan: The distribution of eigenvalues of graphs. Linear Algebra Appl. 216 (1995), 211–224. DOI 10.1016/0024-3795(93)00135-M | MR 1319986
[4] D. M. Cvetković, M. Doob, and H. Sachs: Spectra of Graphs. Academic Press, New York, 1980, third edition Johann Ambrosius Barth Verlag 1995. MR 0572262
[5] D. M. Cvetković, P. Rowlinson: The largest eigenvalue of a graph: a survey. Linear and multilinear Algebra 28 (1990), 3–33. MR 1077731
[6] M. Doob: The limit points of eigenvalues of graphs. Linear Algebra Appl. 114/115 (1989), 659–662. MR 0986899 | Zbl 0671.05050
[7] M. Doob: Some new results on the limit points of eigenvalues of graphs. Abstracts Amer. Math. Soc. 12 (1991), 450.
[8] F. Harary, R. Z. Norman: Some properties of line digraphs. Rend. Circ. Mat. Palermo 9 (1960), 161–168. DOI 10.1007/BF02854581 | MR 0130839
[9] A. J. Hoffman: On limit points of spectral radii of non-negative symmetric integral matrices. Graph Theory and its Application. Lecture Notes in Math. 303, Y. Alavi et al. (eds.), Springer-Verlag, New York, 1972, pp. 165–172. MR 0347860 | Zbl 0297.15016
[10] A. J. Hoffman: On limit points of the least eigenvalue of a graph. Ars Combinatoria 3 (1977), 3–14. MR 0498274 | Zbl 0445.05067
[11] F. R. Gantmacher: Theory of Matrices, Vol. I. AMS Chelsea Publishing, Providence, 1960.
[12] G. Lin, F. Zhang: On the characteristic polynomial of directed line graph and a type of cospectral directed digraph. KeXue TongBao (Chinese Sci. Bulletin) 22 (1983), 1348–1350. MR 0740127
[13] B. Liu, H. Lai: Matrices in Combinatorics and Graph Theory. Kluwer, Dordrecht, 2000.
[14] M. Marcus, H. Minc: A Survey of Matrix Theory and Matrix Inequalities. Allyn and Bacon, Boston, 1964. MR 0162808
[15] J. B. Shearer: On the distribution of the maximum eigenvalue of graphs. Linear Algebra and Appl. 114/115 (1989), 17–20. MR 0986863
[16] F. Zhang, G. Lin, and J. Meng: The characteristic polynomials of digraphs formed by some unary operations. J. Xinjiang Univ. 4 (1987), 1–6. MR 0924475
Search
Partner of
