CONNECTED ROMAN DOMINATION IN GRAPHS

M. H. Muddebihal, Sumangaladevi

Abstract: A Roman dominating function on a graph G is a function f V: 0,1,2 ?{ } satisfying the condition that every vertex u V? for which f u( ) = 0 is adjacent to at least one vertex v V? for which f v( ) 2 = . The weight of a Roman dominating function is the value ( ) ( ) v V f V f v ? = ? . The Roman domination number ? R (G) of G is the minimum weight of a Roman dominating function on G . A Roman dominating function on G is connected Roman dominating function of G if either V V 1 2 ? or V2 is connected. The connected Roman domination number ? RC (G) of G is the minimum weight of a connected Roman dominating function onG . In this paper we establish the upper bounds, lower bounds and some equality results for? RC (G) .

Keywords: Domination number, Roman domination number and Connected Roman domination number

DOI: https://doi.org/10.15623/ijret.2013.0210050