The Steiner k-Wiener index of graphs with given minimum degree

2018/05/11 by Dankelmann, Peter
#05C12 (primary) 92E10 (secondary) #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1805.04571

Abstract

Let G be a connected graph. The Steiner distance d(S) of a set S of vertices is the minimum size of a connected subgraph of G containing all vertices of S. For k∈ ℕ, the Steiner k-Wiener index SW_k(G) is defined as ∑_S d(S), where the sum is over all k-element subsets of the vertex set of G. The average Steiner k-distance μ_k(G) of G is defined as \binomnk^-1 SW_k(G). In this paper we prove upper bounds on the Steiner Wiener index and the average Steiner distance of graphs with given order n and minimum degree δ. Specifically we show that SW_k(G) ≤ (k-1)/(k+1)(3n)/(δ+1) \binomnk + O(n^k), and that μ_k(G) ≤ (k-1)/(k+1)(3n)/(δ+1) + O(1). We improve this bound for triangle-free graphs to SW_k(G) ≤ (k-1)/(k+1)\frac2nδ \binomnk + O(n^k), and μ_k(G) ≤ (k-1)/(k+1)\frac2nδ + O(1). All bounds are best possible.

Related

• Steiner Wiener index of block graphs
• Wiener index and Steiner 3-Wiener index of a graph
• Steiner Distance in Graphs--A Survey
• The inverse problem for the Steiner-Wiener index of trees
• Extremal values for Steiner distances and the Steiner k-Wiener index