An improved bound in Vizing's conjecture

2017/06/12 by Zerbib, Shira · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1706.03682

Abstract

A well-known conjecture of Vizing is that γ(G \square H) ≥ γ(G)γ(H) for any pair of graphs G, H, where γ 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 γ(G \square H) ≥ (1)/(2)γ(G)γ(H) + (1)/(2)min(γ(G),γ(H)). We further improve their result by showing γ(G \square H) ≥ (1)/(2)γ(G)γ(H) + (1)/(2)max(γ(G),γ(H)).

Cited by

• Engineering Dominating Patterns: A Fine-grained Case Study

Related

• Vizing's Conjecture for Almost All Pairs of Graphs
• An Improvement on Vizing's Conjecture
• A brief, simple proof of Vizing's conjecture
• A note on Vizing's conjecture
• On the domination number of the cartesian product of the path graph and any pair of graphs