Name
Title | ||
|---|---|---|
The alternating polynomials and their relation with the spectra and conditional diameters of graphs |
Abstract | ||
|---|---|---|
Given a graph Γ on n = ¦VΓ¦ vertices, the distance between two subgraphs Γ 1 , Γ 2 ⊂ Γ , denoted by ∂ ( Γ 1 , Γ 2 ), is the minimum among the distances between vertices of Γ 1 and Γ 2 . For some integers 1 ⩽ s , t ⩽ n , the conditional ( s , t )- diameter of Γ is then defined as D (s,t) = max Γ 1 , Γ 2 ⊂ Γ {∂(Γ 1 , Γ 2 ): ¦VΓ 1 ¦ = s, ¦VΓ 2 ¦ = t} . Let Γ have distinct eigenvalues λ > λ 1 > λ 2 > … > λ d . For every k = 0, 1, …, d − 1, the k - alternating polynomial P k is defined to be the polynomial of degree k and norm ‖P k ‖∞ = max 1⩽ / ⩽d {¦P k (λ l )¦} = 1 that attains maximum value at λ. These polynomials, which may be thought of as the discrete version of the Chebychev ones, were recently used by the authors to bound the (standard) diameter D ≡ D 1,1 of Γ in terms of its eigenvalues. In this work we derive similar results for conditional diameters. For instance, it is shown that P k (λ)> ‖ν‖ 2 S −1 ⇒ D s,s ⩽k , where v is the (positive) eigenvector associated to λ, with minimum component 1. Similar results are given for locally regular digraphs by using the Laplacian spectrum. Some applications to the study of other parameters, such as the connectivity of Γ, are also discussed. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1016/S0012-365X(96)00235-X | Discrete Mathematics |
Keywords | Field | DocType |
conditional diameter,eigenvalues,eigenvectors | Alternating polynomial,Integer,Discrete mathematics,Graph,Combinatorics,Polynomial,Vertex (geometry),Laplacian spectrum,Spectral line,Mathematics,Eigenvalues and eigenvectors | Journal |
Volume | ISSN | Citations |
167-168, | Discrete Mathematics | 4 |
PageRank | References | Authors |
0.49 | 6 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| M. A. Fiol | 1 | 816 | 87.28 |
| E. Garriga | 2 | 164 | 19.92 |
| J. L.A. Yebra | 3 | 291 | 36.48 |