The degree/Steiner k-diameter problem for trees

Leroy, Golven; Reiswig, Josiah

doi:10.2140/involve.2026.19.259

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

The degree/Steiner $k$-diameter problem for trees

Golven Leroy and Josiah Reiswig

Vol. 19 (2026), No. 2, 259–274

DOI: 10.2140/involve.2026.19.259

Abstract

We extend the degree/diameter problem to the degree/Steiner $k$ -diameter problem. That is, given integers $k \geq 2$ , $d \geq k - 1$ , and $Δ \geq 1$ , we ask for the largest possible order of a graph with maximum degree $Δ$ and Steiner $k$ -diameter $d$ . We then show that, for any tree with order $n$ , Steiner $k$ -diameter $d$ , and maximum degree $Δ$ , the order is bounded by

n \leq {\begin{matrix} 2 & if k = 2 and either Δ = 1 or d = 1, \\ d + 1 & if Δ = 2 and d \geq 2, \\ \frac{Δ {(Δ - 1)}^{ℓ} - 2}{Δ - 2} + (d - k ℓ) {(Δ - 1)}^{ℓ} & if Δ \geq 3 and d \geq k - 1, \end{matrix}

where $ℓ = \min {⌊ \frac{d}{k} - \frac{k - Δ}{k (Δ - 2)} ⌋, ⌊ \frac{d}{k} ⌋},$ and establish that this bound is tight.

Keywords

Steiner distance, degree, diameter, tree

Mathematical Subject Classification

Primary: 05C12

Secondary: 05C05, 05C35, 05C69

Milestones

Received: 6 April 2024

Revised: 4 November 2024

Accepted: 12 November 2024

Published: 8 March 2026

Communicated by Joel Foisy

Authors

Golven Leroy
Graphable Charlotte, NC United States

Josiah Reiswig
Department of Mathematics Anderson University Anderson, SC United States

Vol. 19, No. 2, 2026