کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647815 | 1342377 | 2012 | 5 صفحه PDF | دانلود رایگان |
A path in an edge-colored graph GG, where adjacent edges may have the same color, is a rainbow path if no two edges of the path are colored the same. The rainbow connection number rc(G)rc(G) of GG is the minimum integer kk for which there exists a kk-edge-coloring of GG such that any two distinct vertices of GG are connected by a rainbow path. It is known that for a graph GG with diameter 2, deciding if rc(G)=2rc(G)=2 is NP-Complete. In particular, computing rc(G)rc(G) is NP-hard. So, it is interesting to know the upper bound of rc(G)rc(G) for such a graph GG. In this paper, we show that rc(G)≤5rc(G)≤5 if GG is a bridgeless graph with diameter 2, and that rc(G)≤k+2rc(G)≤k+2 if GG is a connected graph with diameter 2 and has kk bridges, where k≥1k≥1.
Journal: Discrete Mathematics - Volume 312, Issue 8, 28 April 2012, Pages 1453–1457