Dual Connectivity in Graphs - Mohammed A. Mutar; Daniele Ettore Otera; Hasan A. Khawwan (Mathematics)
An edge-coloring <semantics>σ</semantics> of a connected graph G is called rainbow if there exists a rainbow path connecting any pair of vertices. In contrast, <semantics>σ</semantics> is monochromatic if there is a monochromatic path between any two vertices. Some graphs can admit a coloring which is simultaneously rainbow and monochromatic; for instance, any coloring of <semantics>Kn</semantics> is rainbow and monochromatic. This paper refers to such a coloring as dual coloring. We investigate dual coloring on various graphs and raise some questions about the sufficient conditions for connected graphs to be dual connected.