Geodesic
Limit points of eigenvalues of (di)graphs
Czechoslovak Mathematical Journal, Tome 56 (2006) no. 3, pp. 895-902
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 05C50, 15A48
Keywords: limit point; eigenvalue of digraph (graph); double cover; subdivision digraph; line digraph 
@article{CMJ_2006_56_3_a7,
     author = {Zhang, Fuji and Chen, Zhibo},
     title = {Limit points of eigenvalues of (di)graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {895--902},
     year = {2006},
     volume = {56},
     number = {3},
     mrnumber = {2261661},
     zbl = {1164.05412},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2006_56_3_a7/}
}
TY  - JOUR
AU  - Zhang, Fuji
AU  - Chen, Zhibo
TI  - Limit points of eigenvalues of (di)graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2006
SP  - 895
EP  - 902
VL  - 56
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/CMJ_2006_56_3_a7/
LA  - en
ID  - CMJ_2006_56_3_a7
ER  - 
%0 Journal Article
%A Zhang, Fuji
%A Chen, Zhibo
%T Limit points of eigenvalues of (di)graphs
%J Czechoslovak Mathematical Journal
%D 2006
%P 895-902
%V 56
%N 3
%U http://geodesic.mathdoc.fr/item/CMJ_2006_56_3_a7/
%G en
%F CMJ_2006_56_3_a7
Zhang, Fuji; Chen, Zhibo. Limit points of eigenvalues of (di)graphs. Czechoslovak Mathematical Journal, Tome 56 (2006) no. 3, pp. 895-902. http://geodesic.mathdoc.fr/item/CMJ_2006_56_3_a7/

[1] J. A.  Bondy, U. S. R. Murty: Graph Theory with Applications. Macmilliam, London, 1976. | MR

[2] D.  Cao D, H. Yuan: Graphs characterized by the second eigenvalue. J.  Graph Theory 17 (1993), 325–331. | DOI | MR

[3] D. Cao, H. Yuan: The distribution of eigenvalues of graphs. Linear Algebra Appl. 216 (1995), 211–224. | DOI | MR

[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

[5] D. M.  Cvetković, P.  Rowlinson: The largest eigenvalue of a graph: a survey. Linear and multilinear Algebra 28 (1990), 3–33. | MR

[6] M.  Doob: The limit points of eigenvalues of graphs. Linear Algebra Appl. 114/115 (1989), 659–662. | MR | Zbl

[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 | MR

[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 | Zbl

[10] A. J.  Hoffman: On limit points of the least eigenvalue of a graph. Ars Combinatoria 3 (1977), 3–14. | MR | Zbl

[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

[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

[15] J. B.  Shearer: On the distribution of the maximum eigenvalue of graphs. Linear Algebra and Appl. 114/115 (1989), 17–20. | MR

[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