Restrained Italian domination in graphs

Abstract: For a graph

G = (V (G), E (G))

, an Italian dominating function (ID function)

f : V (G) i g h t a r r o w 0, 1, 2

has the property that for every vertex

v i n V (G)

with

f (v) = 0

, either

v

is adjacent to a vertex assigned

2

under

f

or

v

is adjacent to least two vertices assigned

1

under

f

. The weight of an ID function is

s u m_{v i n V (G)} f (v)

. The Italian domination number is the minimum weight taken over all ID functions of

G

. In this paper, we initiate the study of a variant of ID functions. A restrained Italian dominating function (RID function)

f

of

G

is an ID function of

G

for which the subgraph induced by

v i n V (G) m i d f (v) = 0

has no isolated vertices, and the restrained Italian domination number

g a m m a_{r I} (G)

is the minimum weight taken over all RID functions of

G

. We first prove that the problem of computing this parameter is NP-hard, even when restricted to bipartite graphs and chordal graphs as well as planar graphs with maximum degree five. We prove that

g a m m a_{r I} (T)

for a tree

T

of order

n g e q 3

different from the double star

S_{2, 2}

can be bounded from below by

(n + 3) / 2

. Moreover, all extremal trees for this lower bound are characterized in this paper. We also give some sharp bounds on this parameter for general graphs and give the characterizations of graphs

G

with small or large

g a m m a_{r I} (G)

.

Recommendations

Cited in

(17)

This page was built for publication: Restrained Italian domination in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5003499)