Minimum domination conjecture for the augmented Cartesian product
Minimum domination conjecture for the augmented Cartesian product
Let and be graphs, let and be minimum dominating sets of and , respectively, and let denote the graph obtained by the paper's edge-adjoining construction from the edge sets and . The Cartesian product is a dominating set in this augmented graph. Minimum domination conjecture. The set is a minimum dominating set for
The conjecture is the paper's proposed strengthening of the construction's minimality conclusion: it asserts that the dominating set of cardinality is minimum, not merely minimal. The paper states that this conjecture would imply Vizing's conjecture.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Allan van Hulst, “Adjoining edges to GH to construct a minimal dominating set of size γ(G)γ(H)”, arXiv:2111.08371 (2021).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.