Simpler and efficient characterizations of tree t-spanners for graphs with few P4's and (k, l)-graphs

arXiv2208.14309MaRDI QIDQ6409256FDOQ6409256

Authors: F. Couto, Luís Felipe Ignácio Cunha, Diego Ferraz 

Publication date: 30 August 2022

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 tree stretch index. The $t$-admissibility problem aims to decide whether the tree stretch index is at most $t$. Regarding its optimization version, the smallest $t$ for which $G$ is $t$-admissible is the stretch index of $G$, denoted by $sigm{a}_T(G)$. Given a graph with $n$ vertices and $m$ edges, the recognition of $2$-admissible graphs can be done $O(n+m)$ time, whereas $t$-admissibility is NP-complete for $sigm{a}_T(G)leqt$, $tgeq4$ and deciding if $t=3$ is an open problem, for more than 20 years. Since the structural knowledge of classes can be determinant to classify $3$-admissibility's complexity, in this paper we present simpler and faster algorithms to check $2$ and $3$-admissibility for families of graphs with few $P_4$'s and $(k,ell)$-graphs. Regarding $(0,ell)$-graphs, we present lower and upper bounds for the stretch index of these graphs and characterize graphs whose stretch indexes are equal to the proposed upper bound. Moreover, we prove that $t$-admissibility is NP-complete even for line graphs of subdivided graphs.

This page was built for publication: Simpler and efficient characterizations of tree t-spanners for graphs with few P4's and (k, l)-graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6409256)