5
views
0
recommends
+1 Recommend
0 collections
0
shares
• Record: found
• Abstract: found
• Article: found
Is Open Access

# Two inequalities related to Vizing's conjecture

Preprint

Bookmark
There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

### Abstract

A well-known conjecture of Vizing is that $$\gamma(G \square H) \ge \gamma(G)\gamma(H)$$ for any pair of graphs $$G, H$$, where $$\gamma$$ is the domination number and $$G \square H$$ is the Cartesian product of $$G$$ and $$H$$. Suen and Tarr, improving a result of Clark and Suen, showed $$\gamma(G \square H) \ge \frac{1}{2}\gamma(G)\gamma(H) + \frac{1}{2}\min(\gamma(G),\gamma(H))$$. We further improve their result by showing $$\gamma(G \square H) \ge \frac{1}{2}\gamma(G)\gamma(H) + \frac{1}{2}\max(\gamma(G),\gamma(H)).$$ We also prove a fractional version of Vizing's conjecture: $$\gamma(G \square H) \ge \gamma(G)\gamma^*(H)$$.

### Most cited references2

• Record: found

### Vizing's conjecture: a survey and recent results

(2012)
Bookmark
• Record: found

### On the domination of the products of graphs II: Trees

(1987)
Bookmark

### Author and article information

###### Journal
2017-06-12
###### Article
1706.03682