Minimum domination conjecture for the augmented Cartesian product

From papers

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.

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

No solutions have been posted yet.