Steiner 3-diameter, maximum degree and size of a graph
Yaping Mao · International Journal of Computer Mathematics Computer Systems Theory · 2022
The Steiner k-diameter sdiamk(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, sdiam2(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 ℓ.