On a Vizing-type integer domination conjecture

Abstract: Given a simple graph

G

, a dominating set in

G

is a set of vertices

S

such that every vertex not in

S

has a neighbor in

S

. Denote the domination number, which is the size of any minimum dominating set of

G

, by

g a m m a (G)

. For any integer

k g e 1

, a function

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

is called a emph{

k

-dominating function} if the sum of its function values over any closed neighborhood is at least

k

. The weight of a

k

-dominating function is the sum of its values over all the vertices. The

k

-domination number of

G

,

g a m m a_{k} (G)

, is defined to be the minimum weight taken over all

k

-domination functions. Brev{s}ar, Henning, and Klavv{z}ar (On integer domination in graphs and Vizing-like problems. emph{Taiwanese J. Math.} {10(5)} (2006) pp. 1317--1328) asked whether there exists an integer

k g e 2

so that

g a m m a_{k} (G s q u a r e H) g e g a m m a (G) g a m m a (H)

. In this note we use the Roman

2

-domination number,

g a m m a_{R 2}

of Chellali, Haynes, Hedetniemi, and McRae, (Roman

2

-domination. emph{Discrete Applied Mathematics} {204} (2016) pp. 22-28.) to prove that if

G

is a claw-free graph and

H

is an arbitrary graph, then

g a m m a_{2} (G s q u a r e H) g e g a m m a_{R 2} (G s q u a r e H) g e g a m m a (G) g a m m a (H)

, which also implies the conjecture for all

k g e 2

.

Recommendations

Cited in

(2)

This page was built for publication: On a Vizing-type integer domination conjecture

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