An Improvement on Vizing's Conjecture

Details An Improvement on Vizing's Conjecture An Improvement on Vizing's Conjecture

2009-09-21

arxiv.org/abs/0909.3695v1

Mathematics

Combinatorics

4 pages

Scientific paper

Let $\gamma(G)$ denote the domination number of a graph $G$. A {\it Roman domination function} of a graph $G$ is a function $f: V\to\{0,1,2\}$ such that every vertex with 0 has a neighbor with 2. The {\it Roman domination number} $\gamma_R(G)$ is the minimum of $f(V(G))=\Sigma_{v\in V}f(v)$ over all such functions. Let $G\square H$ denote the Cartesian product of graphs $G$ and $H$. We prove that $\gamma(G)\gamma(H) \leq \gamma_R(G\square H)$ for all simple graphs $G$ and $H$, which is an improvement of $\gamma(G)\gamma(H) \leq 2\gamma(G\square H)$ given by Clark and Suen \cite{CS}, since $\gamma(G\square H)\leq \gamma_R(G\square H)\leq 2\gamma(G\square H)$.

Affiliated with

Also associated with

No associations

Rating

An Improvement on Vizing's Conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Improvement on Vizing's Conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Improvement on Vizing's Conjecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-432068