文献类型：期刊文献

英文题名：On rainbow total-coloring of a graph

作者：Sun, Yuefang[1]

机构：[1]Shaoxing Univ, Dept Math, Shaoxing 312000, Zhejiang, Peoples R China

年份：2015

卷号：194

起止页码：171

外文期刊名：DISCRETE APPLIED MATHEMATICS

收录：SCI-EXPANDED(收录号：WOS:000361772500017)、、EI(收录号：20152200897687)、Scopus(收录号：2-s2.0-84940720464)、WOS

基金：We thank the anonymous referees for their careful reading of our work and helpful suggestions. The author was supported by NSFC No. 11401389.

语种：英文

外文关键词：Rainbow total-coloring; Rainbow total-connection number; Nordhaus-Gaddum-type

外文摘要：A path P connecting two vertices u and v in a total-colored graph G is called a rainbow totalpath between u and v if all elements in V(P) boolean OR E(P), except for u and v, are assigned distinct colors. The total-colored graph G is rainbow total-connected if it has a rainbow total-path between every two vertices. The rainbow total-connection number, denoted by rtc(G), of a graph G is the minimum colors such that G is rainbow total-connected. It was shown that rtc(G) <= m(G) + n'(G), and the equality holds if and only if G is a tree, where n'(G) is the number of inner vertices of G. In this paper, we show that rtc(G) not equal m(G) n'(G) - 1, m(G) n'(G) - 2 and characterize the graphs with rtc(G) = m(G) + n'(G) - 3. With this result, the following sharp upper bound holds: for a connected graph G, if G is not a tree, then rtc(G) <= m(G) + n'(G) - 3; moreover, the equality holds if and only if G belongs to five graph classes. We also investigate the Nordhaus-Gaddum-type lower bounds for the rainbow total-connection number of a graph and derive that if G is a connected graph of order n >= 8, then rtc(G) + rtc((G) over bar) >= 6 and rtc(G)rtc((G) over bar) >= 9. An example is given to show that both of these bounds are sharp. (C) 2015 Elsevier B.V. All rights reserved.