Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
488617 | Procedia Computer Science | 2015 | 6 Pages |
Abstract
Let G = (V(G), E(G)) be a nontrivial, finite, and connected graph. Define a k-coloring c : E(G) → {1, 2, ..., n} for some n ∈ N, where two adjacent edges may have the same color. A path from u to v, denoted by u − v path, is said a u − v rainbow path, if there are no two edges in u − v path having the same color. A k-coloring is said a rainbow k-coloring, if every pair of vertices u and v in the V(G) has a u − v rainbow path. The minimum k for which there exists such a k-coloring is defined as the rainbow connection number rc(G) of G.In this paper we introduce two new classes, namely origami graphs and pizza graphs. We determine the rainbow connection number of the graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)