The (α,β,s,t)(α,β,s,t)-diameter of graphs: A particular case of conditional diameter

The conditional diameter of a connected graph Γ=(V,E)Γ=(V,E) is defined as follows: given a property PP of a pair (Γ1,Γ2)(Γ1,Γ2) of subgraphs of ΓΓ, the so-called conditional diameter   or PP-diameter   measures the maximum distance among subgraphs satisfying PP. That is,DP(Γ)≔maxΓ1,Γ2⊂Γ{∂(Γ1,Γ2):Γ1,Γ2satisfyP}.In this paper we consider the conditional diameter in which PP requires that δ(u)⩾αδ(u)⩾α for all u∈V(Γ1)u∈V(Γ1), δ(v)⩾βδ(v)⩾β for all v∈V(Γ2)v∈V(Γ2), |V(Γ1)|⩾s|V(Γ1)|⩾s and |V(Γ2)|⩾t|V(Γ2)|⩾t for some integers 1⩽s,t⩽|V|1⩽s,t⩽|V| and δ⩽α,β⩽Δδ⩽α,β⩽Δ, where δ(x)δ(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)(α,β,s,t)-diameter  . We obtain upper bounds on the (α,β,s,t)(α,β,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.