Inequality Related to Vizing's Conjecture

Let $\gamma(G)$ denote the domination number of a graph $G$ and let $G\square H$ denote the Cartesian product of graphs $G$ and $H$. We prove that $\gamma(G)\gamma(H) \le 2 \gamma(G\square H)$ for all simple graphs $G$ and $H$.

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2000-05, Vol.7 (1)
Main Authors: Clark, W. Edwin, Suen, Stephen
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let $\gamma(G)$ denote the domination number of a graph $G$ and let $G\square H$ denote the Cartesian product of graphs $G$ and $H$. We prove that $\gamma(G)\gamma(H) \le 2 \gamma(G\square H)$ for all simple graphs $G$ and $H$.
ISSN:1077-8926
1077-8926
DOI:10.37236/1542