首页|STRUCTURAL CHARACTERIZATIONS OF TREE t-SPANNERS FOR GRAPHS WITH FEW P_4’S AND (0,ℓ)-GRAPHS

STRUCTURAL CHARACTERIZATIONS OF TREE t-SPANNERS FOR GRAPHS WITH FEW P_4’S AND (0,ℓ)-GRAPHS

扫码查看
原文链接
  • NETL
  • NSTL
  • Edp Sciences S A
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_4’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.

3-admissibility2-admissibilityStretch indexgraphs with few P_4’s(kℓ)-graphsstructural characterization

FERNANDA COUTO、LUIS CUNHA、DIEGO FERRAZ

展开 >

Universidade Federal Rural do Rio de Janeiro, Av. Gov. Roberto Silveira, s/n - Moqueta, Nova Iguacu, Brazil

Universidade Federal Fluminense, Av. Gal. Milton Tavares de Souza, s/n - Sao Domingos, Niteroi, Brazil

Universidade Federal do Rio de Janeiro, Av. Horacio Macedo 2030, Centro de Tecnologia, Cidade Universitaria, Rio de Janeiro, Brazil

2025

10.1051/ro/2025012

RAIRO operations research

RAIRO operations research

ISSN：0399-0559
年,卷(期)：2025.59(2)
  • 22