## Abstract

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.

Original language | English |
---|---|

Article number | 112468 |

Journal | Discrete Mathematics |

Volume | 344 |

Issue number | 8 |

DOIs | |

Publication status | Published - Aug 2021 |

## Keywords

- Diameter
- Maximum degree
- Size
- Steiner diameter
- Steiner distance

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics