Hardness and efficiency on t-admissibility for graph operations

The t -admissibility problem aims to decide whether a graph G has a spanning tree T in which the distance between any two adjacent vertices of G is at most t . In this case, G is called t -admissible, and the smallest t for which G is t -admissible is the stretch index of G . A complementary prism of G , denoted by G G ¯ , is obtained by the union of G with its complement G ¯ and the addition of a perfect matching between corresponding vertices of G and G ¯ . One of the challenges of the t -admissibility problem is to determine 3-admissible graph classes, since the computational complexity of such a problem remains open for more than 25 years. Moreover, it is known that recognizing 4-admissible graphs is, in general, an NP -complete problem (Cai and Corneil, 1995), as well as recognizing t -admissible graphs for graphs with diameter at most t + 1 , for t ≥ 4 (Papoutsakis, 2013). We prove that any graph G , non-complete graph, can be transformed into a 4-admissible one, by obtaining G G ¯ . Furthermore, we prove that the stretch indexes of G G ¯ graphs are equal to 4, and since they have diameter at most t + 1 , we present a class for which t -admissibility is solved in polynomial time. G G graphs are the Cartesian product G × K 2 , defined by the union of two copies of G and the addition of a perfect matching between corresponding vertices of the two graphs G . Interestingly, we prove that for G G graphs, whose definition is very similar to G G ¯ ’s, t -admissibility is NP -complete. Generalizing these constructions, we prove that determining t -admissibility is NP -complete for graphs that have perfect matching.