Minimum domination conjecture for the augmented Cartesian product

At least 4 years old · documented by

Let GG and HH be graphs, let DGD_G and DHD_H be minimum dominating sets of GG and HH, respectively, and let AG,H[FG,FH]A_{G,H}[F_G,F_H] denote the graph obtained by the paper's edge-adjoining construction from the edge sets FGF_G and FHF_H. The Cartesian product DG×DHD_G\times D_H is a dominating set in this augmented graph. Minimum domination conjecture. The set DG×DHD_G\times D_H is a minimum dominating set for

AG,H[FG,FH].A_{G,H}[F_G,F_H].

The conjecture is the paper's proposed strengthening of the construction's minimality conclusion: it asserts that the dominating set of cardinality γ(G)γ(H)\gamma(G)\gamma(H) 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

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.