Structural characterizations of tree t-spanners for graphs with few P₄’s and (0, ℓ)-graphs^*

¹ Universidade Federal Rural do Rio de Janeiro, Av. Gov. Roberto Silveira, s/n – Moquetá, Nova Iguaçu, Brazil
² Universidade Federal Fluminense, Av. Gal. Milton Tavares de Souza, s/n – S˜ao Domingos, Niterói, Brazil
³ Universidade Federal do Rio de Janeiro, Av. Horácio Macedo 2030, Centro de Tecnologia, Cidade Universitária, Rio de Janeiro, Brazil

^* Corresponding author: lfignacio@ic.uff.br

Received: 18 April 2024
Accepted: 10 February 2025

Abstract

A tree t-spanner of a graph G is a spanning tree T in which the distance between any two adjacent vertices of G is at most t. The smallest t for which G has a tree t-spanner is called the tree stretch index of G, denoted by σ_T (G) = t. The objective of the t-admissibility problem is to determine whether the tree stretch index of a graph, denoted by σ_T (G), is less than or equal to a given value t. Given a graph with n vertices and m edges, the recognition of 2-admissible graphs can be accomplished in O(n + m) time. In contrast, t-admissibility is NP-complete for t ≥ 4. Furthermore, determining whether t = 3 remains an open problem, despite more than two decades of research. Given the pivotal role structural knowledge plays in classifying the complexity of 3-admissibility, this paper presents structural characterizations that yield simpler and faster algorithms for checking 2 and 3-admissibility in families of graphs with few P₄’s and (k, ℓ)-graphs. Furthermore, with regard to (0, ℓ)-graphs, we present lower and upper bounds on the tree stretch index of these graphs and characterize graphs whose tree stretch indexes are equal to the proposed upper bound. Finally, we prove that t-admissibility is NP-complete even for line graphs of subdivided graphs.