The Rainbow Connection Number of Origami Graphs and Pizza Graphs

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.