Minimizing Distances Between Vertices and Edges Through Tree t-Spanners

A tree t-spanner of a graph G is a spanning tree T of G in which any two adjacent vertices of G have distance at most t in T. We say that G is t-admissible if it admits a tree t-spanner, and \(\sigma \) is the smallest t for which G is t-admissible. It is well-known that deciding whether G has a tree t-spanner (the t -admissibility problem) is in \(\textsf{P}\) for \(t\le 2\) , it is \(\textsf{NP}\) -complete for \(t\ge 4\) , and it is a long open problem to decide 3-admissibility. Edge t -admissibility is a variation of the former problem, where the goal is decide whether the line graph of G contains a tree t-spanner T, indicating that adjacent edges of G have distance at most t in T. It is known that edge t -admissibility is in \(\textsf{P}\) for \(t \le 3\) , while it is \(\textsf{NP}\) -complete for \(t\ge 8\) . We investigate the complexity of dealing with minimizing distances at same time vertices and edges. This is the Total admissibility problem. We prove that total t -admissibility is \(\textsf{NP}\) -complete, even for bipartite or planar graphs. Besides, total graphs include middle-graphs and almost-total graphs as subgraphs, which satisfy the operation we define as clique-augmenting of graphs G, denoted as CA(G). We prove that deciding tree t -admissibility for clique-augmenting graphs is \(\textsf{NP}\) -complete. We also prove that graphs CA(G) can be classified into two types ( \(\sigma (CA(G)) = \sigma (G)\) or \(\sigma (CA(G)) = \sigma (G) +1\) ) and it is \(\textsf{NP}\) -complete to decide whether \(\sigma (CA(G)) = \sigma (G)\) . Moreover, by showing special properties, we present several tractable cases to obtain \(\sigma (CA(G))\) .