Steiner 3-diameter, maximum degree and size of a graph. Issue 2 (3rd April 2022) - Mao, Yaping
Abstract : The Steiner k -diameter sdiam k ⁡ ( G ) of a graph G, introduced by Chartrand, Oellermann, Tian and Zou in 1989, is a natural generalization of the concept of classical diameter. When k  = 2, sdiam 2 ⁡ ( G ) = diam ( G ) is the classical diameter. The problem of determining the minimum size of a graph of order n whose diameter is at most d and whose maximum degree is ℓ was first introduced by Erdös and Rényi. In this paper, we generalize the above problem for Steiner k -diameter, and study the problem of determining the minimum size of a graph of order n whose Steiner 3-diameter is at most d and whose maximum degree is at most ℓ.