Hardness result for the total rainbow k-connection of graphs

Wenjing Li, Xueliang Li and Di Wu

Applied Mathematics and Computation, 2017, vol. 305, issue C, 27-31

Abstract: 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.

Keywords: Total-rainbow k-connection number; Computational complexity; NP-complete (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300317300942
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:305:y:2017:i:c:p:27-31

DOI: 10.1016/j.amc.2017.01.068

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().