Steiner diameter, maximum degree and size of a graph

Let G be a connected graph of order n. The Steiner distance d_G(S) of a set S of vertices is the minimum size of a connected subgraph of G that contains all vertices of S. For k≤n, the Steiner k-diameter sdiam_k(G) of G is the maximum Steiner distance among all sets of k vertices of G. The Steiner k-diameter generalises the classical diameter, which coincides with the Steiner 2-diameter. The problem of determining the minimum size of a graph of given order, diameter and maximum degree was first studied by Erdös and Rényi. In this paper we consider the corresponding problem for the Steiner k-diameter. For k,Δ,d,n∈N define e_k(n,Δ,d) as the minimum size of a graph of given order n, maximum degree Δ and Steiner k-diameter at most d, if such a graph exists. The study of this problem for the special case k=3 was initiated in a recent paper by Mao. In this paper we determine e_k(n,Δ,d) for k∈{n,n−1,n−2}. For the case k=n−3 we prove that e_n−3(n,Δ,n−3)=⌈[Formula presented](n−1)+[Formula presented]Δ⌉ if Δ≤[Formula presented], and also that e_n−3(n,Δ,n−3)=⌈[Formula presented]n−[Formula presented]Δ⌉ if Δ≥[Formula presented]. We further show that e_k(n,Δ,d)=n−1 for, approximately, d≥klog_Δ−1⁡(n+2), and determine e_k(n,Δ,k−1) for all k with 2≤k≤n.