PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 2 | 355-362
Tytuł artykułu

Hardness Results for Total Rainbow Connection of Graphs

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
36
Numer
2
Strony
355-362
Opis fizyczny
Daty
wydano
2016-05-01
otrzymano
2015-03-10
poprawiono
2015-07-07
zaakceptowano
2015-07-07
online
2016-04-15
Twórcy
autor
  • School of Mathematics Science Huaqiao University Quanzhou 362021, China, lily60612@126.com
autor
  • Department of Mathematics Qinghai Normal University Xining, 810008, China, hbf@qhnu.edu.cn
autor
  • College of Mathematics and Information Science Henan Normal University Xinxiang 453007, China, mayingbincw@htu.cn
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1856
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.