Spectral characterizations of anti-regular graphs
| Autor: | Joon-yeob Lee, Eric Piato, Barbara J. Schweitzer, Cesar O. Aguilar |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Numerical Analysis
Threshold graph Chebyshev polynomials Algebra and Number Theory 0211 other engineering and technologies Asymptotic distribution 021107 urban & regional planning 010103 numerical & computational mathematics 02 engineering and technology Mathematics::Spectral Theory 01 natural sciences Graph Combinatorics 05C50 15B05 05C75 15A18 FOS: Mathematics Bipartite graph Mathematics - Combinatorics Discrete Mathematics and Combinatorics Combinatorics (math.CO) Geometry and Topology 0101 mathematics Trigonometry Eigenvalues and eigenvectors Mathematics |
| Zdroj: | Linear Algebra and its Applications. 557:84-104 |
| ISSN: | 0024-3795 |
| Popis: | We study the eigenvalues of the unique connected anti-regular graph $A_n$. Using Chebyshev polynomials of the second kind, we obtain a trigonometric equation whose roots are the eigenvalues and perform elementary analysis to obtain an almost complete characterization of the eigenvalues. In particular, we show that the interval $\Omega=[\tfrac{-1-\sqrt{2}}{2}, \tfrac{-1+\sqrt{2}}{2}]$ contains only the trivial eigenvalues $\lambda = -1$ or $\lambda=0$, and any closed interval strictly larger than $\Omega$ will contain eigenvalues of $A_n$ for all $n$ sufficiently large. We also obtain bounds for the maximum and minimum eigenvalues, and for all other eigenvalues we obtain interval bounds that improve as $n$ increases. Moreover, our approach reveals a more complete picture of the bipartite character of the eigenvalues of $A_n$, namely, as $n$ increases the eigenvalues are (approximately) symmetric about the number $-\tfrac{1}{2}$. We also obtain an asymptotic distribution of the eigenvalues as $n\rightarrow\infty$. Finally, the relationship between the eigenvalues of $A_n$ and the eigenvalues of a general threshold graph is discussed. Comment: 20 pages, 6 figures, 1 table |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect