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 t...

Full description

Saved in:
Bibliographic Details
Published in:Procedia computer science 2015, Vol.74, p.162-167
Main Authors: Nabila, S., Salman, A.N.M.
Format: Article
Language:English
Subjects:
Edge coloring
origami graph
pizza graph
rainbow coloring
rainbow connection number
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1877-0509
1877-0509
DOI:10.1016/j.procs.2015.12.093