2017/04/15 by Mao, Yaping, Wang, Zhao · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1704.04695
The Steiner 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 is ℓ was first introduced by Erdös and Rényi. Recently, Mao considered the problem of determining the minimum size of a graph of order n whose Steiner k-diameter is at most d and whose maximum is at most ℓ, where 3≤ k≤ n, and studied this new problem when k=3. In this paper, we investigate the problem when n-3≤ k≤ n.