Roman domination in graphs with minimum degree at least two and some forbidden cycles

Authors Seyed Mahmood Sheikholeslami, Mustapha Chellali, R. Khoeilar, Hossein Karami, Zehui Shao

Publication date 14 October 2021

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: Let

G = (V, E)

be a graph of order

n

and let

g a m m a_{R} (G)

and

p a r t i a l (G)

denote the Roman domination number and the differential of

G,

respectively. In this paper we prove that for any integer

k g e q 0

, if

G

is a graph of order

n g e q 6 k + 9

, minimum degree

d e l t a g e q 2,

which does not contain any induced

C_{5}, C_{8}, l d o t s, C_{3 k + 2}

% -cycles, then

g a m m a_{R} (G) l e q f r a c (4 k + 8) n 6 k + 11

. This bound is an improvement of the bounds given in [E.W. Chambers, B. Kinnersley, N. Prince, and D.B. West, Extremal problems for Roman domination, SIAM J. Discrete Math. 23 (2009) 1575--1586] when

k = 0,

{and [S. Bermudo, On the differential and Roman domination number of a graph with minimum degree two, Discrete Appl. Math. 232 (2017), 64--72] when }

k = 1.

Moreover, using the Gallai-type result involving the Roman domination number and the differential of graphs established by Bermudo et al. stating that

g a m m a_{R} (G) + p a r t i a l (G) = n

, we have

p a r t i a l (G) g e q f r a c (2 k + 3) n 6 k + 11,

thereby settling the conjecture of Bermudo posed in the second paper.

This page was built for publication: Roman domination in graphs with minimum degree at least two and some forbidden cycles

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