Vizing's Conjecture for Almost All Pairs of Graphs

Author name not available (Why is that?)

Publication date: 2 February 2015

Abstract: For any graph

G = (V, E)

, a subset

S s u b s e t e q V

d o m i n a t e s

G

if all vertices are contained in the closed neighborhood of

S

, that is

N [S] = V

. The minimum cardinality over all such

S

is called the domination number, written

g a m m a (G)

. In 1963, V.G. Vizing conjectured that

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

where

s q u a r e

stands for the Cartesian product of graphs. In this note, we prove that if

l e f t | G i g h t | g e q g a m m a (G) g a m m a (H)

and

l e f t | H i g h t | g e q g a m m a (G) g a m m a (H)

, then the conjecture holds. This result quickly implies Vizing's conjecture for almost all pairs of graphs

G, H

with

l e f t | G i g h t | g e q l e f t | H i g h t |

, satisfying

l e f t | G i g h t | l e q q^{f r a c l e f t | H i g h t | l o g_{q} l e f t | H i g h t |}

for

q = f r a c 1 1 - p

and

p

the edge probability of the ErdH{o}s-R'enyi random graph.

This page was built for publication: Vizing's Conjecture for Almost All Pairs of Graphs