The (a,b,s,t)-diameter of graphs: a particular case of conditional diameter

الأصل · EN

The conditional diameter of a connected graph Γ=(V,E) is defined as follows: given a property P of a pair (Γ₁, Γ₂) of subgraphs of Γ, the so-called conditional diameter or P- diameter measures the maximum distance among subgraphs satisfying P. That is, D P(Γ):=ᵧ₁, ᵧ₂⊂ ᵧ {∂(Γ₁, Γ₂): Γ₁, Γ₂ satisfy P}. In this paper we consider the conditional diameter in which P requires that δ(u)≥ α for all u∈ V(Γ₁), δ(v)≥ β for all v∈ V(Γ₂), | V(Γ₁)| ≥ s and | V(Γ₂)| ≥ 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.