A new bound for Vizing's conjecture

Author name not available (Why is that?)

Publication date: 6 August 2016

Abstract: For any graph

G

, we define the power

p i (G)

as the minimum of the largest number of neighbors in a

g a m m a

-set of

G

, of any vertex, taken over all

g a m m a

-sets of

G

. We show that

g a m m a (G s q u a r e H) g e q f r a c p i (G) 2 p i (G) - 1 g a m m a (G) g a m m a (H)

. This implies that for any graphs

G

and

H

,

g a m m a (G s q u a r e H) g e q f r a c g a m m a (G) 2 g a m m a (G) - 1 g a m m a (G) g a m m a (H)

, and if

G

is claw-free or

P_{4}

-free,

g a m m a (G s q u a r e H) g e q f r a c 23 g a m m a (G) g a m m a (H)

, where

g a m m a (G)

is the domination number of

G

.

This page was built for publication: A new bound for Vizing's conjecture