Hardness Results for Total Rainbow Connection of Graphs

• Autorzy: Lily Chen , Bofeng Huo , Yingbin Ma
• Języki publikacji: EN

Abstrakty

EN

A total-colored path is total rainbow if both its edges and internal vertices have distinct colors. The total rainbow connection number of a connected graph G, denoted by trc(G), is the smallest number of colors that are needed in a total-coloring of G in order to make G total rainbow connected, that is, any two vertices of G are connected by a total rainbow path. In this paper, we study the computational complexity of total rainbow connection of graphs. We show that deciding whether a given total-coloring of a graph G makes it total rainbow connected is NP-Complete. We also prove that given a graph G, deciding whether trc(G) = 3 is NP-Complete.

Słowa kluczowe

EN

total rainbow connection; computational complexity

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 2
• Strony: 355-362

Daty

wydano

2016-05-01

otrzymano

2015-03-10

poprawiono

2015-07-07

zaakceptowano

2015-07-07

online

2016-04-15

Twórcy

autor

Lily Chen

• School of Mathematics Science Huaqiao University Quanzhou 362021, China

autor

Bofeng Huo

• Department of Mathematics Qinghai Normal University Xining, 810008, China

autor

Yingbin Ma

• College of Mathematics and Information Science Henan Normal University Xinxiang 453007, China

Identyfikatory

DOI

10.7151/dmgt.1856