Total Rainbow Connection Number and Complementary Graph
Total Rainbow Connection Number and Complementary Graph
复制标题
DOI：
10.1007/s00025-015-0469-8
复制
发表时间：
2016-09
影响因子：
2.2
通讯作者：
Yingbin Ma
中科院分区：
文献类型：
--
作者：
Yingbin Ma
如果任何两个不同的顶点通过其内部顶点具有不同颜色的路径连接在一起，则一个顶点着色图G是连接的彩虹顶点。彩虹顶点连接数G，用RVC(G)表示，是使Grainrow顶点连通所需的最小颜色数。本文证明了对于连通图G，如果，则，这个界是紧的。接下来，我们得到了对于无三角形的图，如果图是连通的，那么，这个界是紧的。如果一条全色路径的边和内部顶点具有不同的颜色，则它是全彩虹。如果任何两个不同的顶点通过某条全彩虹路径相连，则称全彩虹图G是全彩虹连通的。用TRC(G)表示的G的总彩虹连通数是为了使G的总彩虹连通而给G的边和顶点着色所需的最小颜色数。在本文中，我们证明了对于一个没有三角形的图，IFG是连通的，然后是TRC，并且这个界是紧的。接下来，提供彩虹连接总数的Nordhaus-Gadum型结果。我们证明了如果G和G是连通的，则举例说明了当n=5时，这个下界是紧的。当n=4，6时，也给出了紧的下界。
A vertex-colored graphGis rainbow vertex connected if any two distinct vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex connection number ofG, denoted by rvc(G), is the smallest number of colors that are needed in order to makeGrainbow vertex connected. In this paper, we prove that for a connected graphG, if, then, and this bound is tight. Next, we obtain that for a triangle-free graphwith, ifGis connected, then, and this bound is tight. A total-colored path is total rainbow if its edges and internal vertices have distinct colors. A total-colored graphGis total rainbow connected if any two distinct vertices are connected by some total rainbow path. The total rainbow connection number ofG, denoted by trc(G), is the smallest number of colors required to color the edges and vertices ofGin order to makeGtotal rainbow connected. In this paper, we prove that for a triangle-free graphwith, ifGis connected, then trc, and this bound is tight. Next, a Nordhaus–Gaddum-type result for the total rainbow connection number is provided. We show that ifGandare both connected, thenExamples are given to show that the lower bound is tight forandn= 5. Tight lower bounds are also given forn= 4, 6.