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.
References
Primary source
Allan van Hulst, “Adjoining edges to GH to construct a minimal dominating set of size γ(G)γ(H)”, arXiv:2111.08371 (2021).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.