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
- Allan van Hulst, “Adjoining edges to GH to construct a minimal dominating set of size γ(G)γ(H)”, arXiv:2111.08371 (2021).
Progress summary
Never refreshed
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.