Hardness result for the total rainbow k-connection of graphs

摘要

A total-coloring of a graph G is a coloring of both the edge set E(G) and the vertex set V(G) of G. A path in a total-colored graph is called total-rainbow if its edges and internal vertices have distinct colors. For a positive integer k, a total-colored graph is called total-rainbow k-connected if for every two vertices of G there are k internally disjoint total-rainbow paths in G connecting them. For an ℓ-connected graph G and an integer k with 1 ≤ k ≤ ℓ, the total-rainbow k-connection number of G, denoted by trck(G), is the minimum number of colors needed in a total-coloring of G to make G total-rainbow k-connected. In this paper, we study the computational complexity of total-rainbow k-connection number of graphs. We show that it is NP-complete to decide whether trck(G)=3 for any fixed positive integer k.