Vizing-like conjecture for the upper domination of Cartesian products of graphs -- the proof

MaRDI QIDQ2571305zbMATH OpenFDO

Authors Boštjan Brešar

Publication date 1 November 2005

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.emis.de/journals/EJC/Volume_12/Abstracts/v12i1n12.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

Summary: We prove the following conjecture of \textit{R. J. Nowakowski} and \textit{D. F. Rall} [Discuss. Math., Graph Theory 16, 53--79 (1996; Zbl 0865.05071)]: For arbitrary graphs \(G\) and \(H\) the upper domination number of the Cartesian product \(G\square H\) is at least the product of their upper domination numbers, in symbols: \(\Gamma(G\square H)\geq \Gamma(G)\Gamma(H)\).

Recommendations

• A result on Vizing's conjecture
• An inequality related to Vizing's conjecture
• Improving some bounds for dominating Cartesian products
• On Vizing's conjecture
• Vizing's conjecture for graphs with domination number 3 -- a new proof

Cited in

(10)

• On the total \(\{k\}\)-domination number of Cartesian products of graphs
• Edge weighting functions on semitotal dominating sets
• Tightness of domination inequalities for direct product graphs
• Alliance free sets in Cartesian product graphs
• On independent domination in direct products
• scientific article; zbMATH DE number 1124600 (Why is no real title available?)
• Domination-related parameters in rooted product graphs
• Some results on Vizing's conjecture and related problems
• Dominating direct products of graphs
• On the upper total domination number of Cartesian products of graphs

This page was built for publication: Vizing-like conjecture for the upper domination of Cartesian products of graphs -- the proof

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