An improved bound in Vizing's conjecture

DOI10.1007/S00373-019-02083-6MaRDI QIDQ2287733zbMATH OpenOpenAlexWikidataFDO

Authors Shira Zerbib

Publication date 21 January 2020

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.03682

zbMATH Keywords

Cartesian productgraph dominationVizing's conjecture

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Abstract: A well-known conjecture of Vizing is that $gamma(GsquareH)gegamma(G)gamma(H)$ for any pair of graphs $G,H$, where $gamma$ is the domination number and $GsquareH$ is the Cartesian product of $G$ and $H$. Suen and Tarr, improving a result of Clark and Suen, showed $gamma(GsquareH)gefrac12gamma(G)gamma(H)+frac12min(gamma(G),gamma(H))$. We further improve their result by showing $gamma(GsquareH)gefrac12gamma(G)gamma(H)+frac12max(gamma(G),gamma(H)).$

Recommendations

• An improvement on Vizing's conjecture
• An improved inequality related to Vizing's conjecture
• Some improved inequalities related to Vizing's conjecture
• A result on Vizing's conjecture
• An Improvement in the Two-packing Bound Related to Vizing's Conjecture
• Improved bounds on a generalization of Tuza's conjecture
• Some results on Vizing's conjecture and related problems
• On Vizing's conjecture
• scientific article; zbMATH DE number 140092
• An improved bound in Wirsing's problem

Cites work

• A Vizing-type result for semi-total domination
• An improved inequality related to Vizing's conjecture
• An inequality related to Vizing's conjecture
• scientific article; zbMATH DE number 3715623 (Why is no real title available?)
• scientific article; zbMATH DE number 1124600 (Why is no real title available?)
• scientific article; zbMATH DE number 3308993 (Why is no real title available?)
• Improving the Clark-Suen bound on the domination number of the Cartesian product of graphs
• Vizing's conjecture: a survey and recent results

Cited in

(22)

• An improved upper bound for Leo Moser's worm problem
• A result on Vizing's conjecture
• An inequality related to Vizing's conjecture
• Some improved inequalities related to Vizing's conjecture
• An improvement on Vizing's conjecture
• Improving the Clark-Suen bound on the domination number of the Cartesian product of graphs
• Towards a computational proof of Vizing's conjecture using semidefinite programming and sums-of-squares
• An improvement to the Hilton-Zhao vertex-splitting conjecture
• A new framework to approach Vizing's conjecture
• An improved inequality related to Vizing's conjecture
• Improving the use of cyclic zippers in finding lower bounds for van der Waerden numbers
• An Improvement in the Two-packing Bound Related to Vizing's Conjecture
• An Optimization-Based Sum-of-Squares Approach to Vizing's Conjecture
• scientific article; zbMATH DE number 2197881 (Why is no real title available?)
• On construction for trees making the equality hold in Vizing's conjecture
• Domination in digraphs and their direct and Cartesian products
• Sum-of-squares certificates for Vizing's conjecture via determining Gröbner bases
• An improved bound for the Manickam-Miklós-Singhi conjecture
• Domination number of Cartesian product through space projections
• Domination number of modular product graphs
• Some results on Vizing's conjecture and related problems
• A lower bound for the domination number of triple Cartesian products of graphs

This page was built for publication: An improved bound in Vizing's conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2287733)