STRUCTURAL PROPERTIES OF SIGNED GRAPHS ADMITTING ROMAN DOMINATING FUNCTION

STRUCTURAL PROPERTIES OF SIGNED GRAPHS ADMITTING ROMAN DOMINATING FUNCTION

J. Joseph , M. Joseph

[PDF]

Abstract

A Roman dominating function(RDF) on a signed graph S = (G, σ) is a function f : V (S) → {0, 1, 2} such that (i) f(N[v]) = f(v) + P u∈N(v) σ(uv)f(u) ≥ 1 for every vertex v ∈ V (S) and (ii) for any vertex v with f(v) = 0 there exists a vertex u ∈ N+(v) having f(u) = 2. In this article we explore structural properties of signed graphs admitting an RDF. Further, signed graphs with 3-regular graph as their underlying graph are examined and characterisation of one of its subclasses, net-regular signed graphs admitting an RDF is obtained.

Keywords

signed graphs, roman dominating function, roman domination number.