A study on dominating functions in signed graphs

Abstract

In this thesis, a study on Roman dominating functions in the realm of signed graphs is carried out. Unlike graphs, not all signed graphs admit a Roman dominating function, which leads to the primary problem of exploring signed graphs admitting a Roman dominating function. Further, variants of dominating function such as Roman {2}-dominating function, Minus dominating function and Signed dominating function in signed graphs are also studied. A dominating set of a signed graph S is dened as a set D and#8838; V such that each vertex v and#8712; V \ D has at least one neighbour u and#8712; D with and#963;(uv) = 1. The domination number and#947;(S) is the minimum cardinality among all the dominating sets newlineof S. A characterisation for minimal dominating sets of a signed graph along with newlinecharacterisations of signed graphs with domination number k, where 1 and#8804; k and#8804; 4 and newlinen and#8722; 2 and#8804; k and#8804; n are obtained. A Roman dominating function(RDF) on a signed graph S = (G, and#963;) is a function f : V (S) and#8594; {0, 1, 2} having the properties that (i) for every vertex u and#8712; V (G), f(N[u]) = f(u) + Pvand#8712;N (u) and#963;(uv)f(v) and#8805; 1 and (ii) for each vertex u and#8712; V (G) with f(u) = 0, there exists a vertex v and#8712; N +(u) having f(v) = 2. The signed graphs newlineadmitting an RDF are explored and certain classes of signed graphs such as paths, newlinecycles, stars admitting an RDF are characterised. Further, structural properties of signed graphs with 3-regular underlying graphs that admit an RDF are presented newlineand a characterisation of net-regular signed graphs with 3-regular underlying graphs, newlineadmitting an RDF is obtained. The signed graphs with Roman domination number equal to 2, 3, 4 and n are characterised. Further, criticality concepts have been examined by studying and#947;R-edge critical signed graphs S for which and#947;R(S +e) lt and#947;R(S), where the signature of the edge e is 1. A characterisation of and#947;R-edge critical signed trees with a single negative edge is presented, apart from some general results on and#947;R-edge critical signed graphs.