A Combinatorial Approach to Study the Nordhaus–Guddum-Type Results for Steiner Degree Distance

Abstract

In 1994, Dobrynin and Kochetova introduced the concept of degree distance DD(Γ) of a connected graph Γ. Let dΓ(S) be the Steiner k-distance of S⊆V(Γ). The Steiner Wiener k-index or k-center Steiner Wiener indexSWk(Γ) of Γ is defined by SWk(Γ)=∑|S|=kS⊆V(Γ)dΓ(S). The k-center Steiner degree distanceSDDk(Γ) of a connected graph Γ is defined by SDDk(Γ)=∑|S|=kS⊆V(Γ)∑v∈SdegΓ(v)dΓ(S), where degΓ(v) is the degree of the vertex v in Γ. In this paper, we consider the Nordhaus–Gaddum-type results for SWk(Γ) and SDDk(Γ). Upper bounds on SWk(Γ)+SWk(Γ¯) and SWk(Γ)·SWk(Γ¯) are obtained for a connected graph Γ and compared with previous bounds. We present sharp upper and lower bounds of SDDk(Γ)+SDDk(Γ¯) and SDDk(Γ)·SDDk(Γ¯) for a connected graph Γ of order n with maximum degree Δ and minimum degree δ. Some graph classes attaining these bounds are also given.

Keywords

• distance
• Steiner distance
• degree distance
• Steiner Wiener <i>k</i>-index
• <i>k</i>-center Steiner degree distance
• Nordhaus–Gaddum-type result