The alternating polynomials and their relation with the spectra and conditional diameters of graphs Original Research Article

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 Pk is defined to be the polynomial of degree k and norm ‖Pk‖∞ = max1⩽ / ⩽d {¦Pk(λ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 ≡ D1,1 of Γ in terms of its eigenvalues. In this work we derive similar results for conditional diameters. For instance, it is shown that Pk(λ)>‖ν‖2S−1 ⇒ Ds,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.