کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4626937 | 1631796 | 2015 | 7 صفحه PDF | دانلود رایگان |
A path in an edge-colored graph is said to be a rainbow path if no two edges on the path share the same color. An edge-colored graph is (strongly) rainbow connected if there exists a rainbow (geodesic) path between every pair of vertices. The (strong) rainbow connection number of G , denoted by (scr(G)scr(G), respectively) rc(G)rc(G), is the smallest number of colors that are needed in order to make G (strongly) rainbow connected. A vertex-colored graph G is rainbow vertex-connected if any pair of vertices in G are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection number of a connected graph G , denoted by rvc(G)rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. Though for a general graph G it is NP-Complete to decide whether rc(G)=2rc(G)=2 (or rvc(G)=2rvc(G)=2), in this paper, we show that the problem becomes easy when G is a bipartite graph. Whereas deciding whether rc(G)=3rc(G)=3 (or rvc(G)=3rvc(G)=3) is still NP-Complete, even when G is a bipartite graph. Moreover, it is known that deciding whether a given edge(vertex)-colored (with an unbound number of colors) graph is rainbow (vertex-) connected is NP-Complete. We will prove that it is still NP-Complete even when the edge(vertex)-colored graph is bipartite. We also show that a few NP-hard problems on rainbow connection are indeed NP-Complete.
Journal: Applied Mathematics and Computation - Volume 258, 1 May 2015, Pages 155–161