2006/02/20 by J. A. Rodriguez · 1 citation
Mathematics · #math.CO #msc:05C12 #msc:05C50 #msc:15A18
paper · pdf · doi:10.1016/j.dam.2006.04.001
published as Discrete Applied Mathematics 154 (14) (2006) 2024-2031
arxiv created 2006/02/20 · arxiv updated 2009/12/01
The conditional diameter of a connected graph Γ=(V,E) is defined as follows: given a property \cal P of a pair (Γ1, Γ2) of subgraphs of Γ, the so-called conditional diameter or \cal P-\em diameter measures the maximum distance among subgraphs satisfying \cal P. That is, D\cal P(Γ):=maxΓ1, Γ2⊂ Γ \∂(Γ1, Γ2): Γ1, Γ2 \rm satisfy \cal P\. In this paper we consider the conditional diameter in which \cal P requires that δ(u)≥ α for all u∈ V(Γ1), δ(v)≥ β for all v∈ V(Γ2), | V(Γ1)| ≥ s and | V(Γ2)| ≥ t for some integers 1≤ s,t≤ |V| and δ≤ α, β≤ Δ, where δ(x) denotes the degree of a vertex x of Γ, δ denotes the minimum degree and Δ the maximum degree of Γ. The conditional diameter obtained is called (α,β, s,t)-diameter. We obtain upper bounds on the (α,β, s,t)-diameter by using the k-alternating polynomials on the mesh of eigenvalues of an associated weighted graph. The method provides also bounds for other parameters such as vertex separators.