The weaker Vizing conjecture for layer projections contained in minimum dominating sets

About 4 years old · traced to

Let GG and HH be graphs, let G□HG\Box H be their Cartesian product, and let DD be a dominating set of G□HG\Box H. For each h∈V(H)h\in V(H), let GhG_h be the GG-layer corresponding to hh, and let pGp_G denote projection onto GG. The weaker Vizing conjecture. If, for every h∈V(H)h\in V(H), there is a minimum dominating set DhD_h of GG such that

pG(D∩Gh)⊆Dh,p_G(D\cap G_h)\subseteq D_h,

then

∣D∣≥γ(G)γ(H).|D|\geq \gamma(G)\gamma(H).

This is a special case of Vizing's conjecture, motivated by the paper's discussion of vertically undominated cells and equality in the general half-bound; the paper establishes related special cases but leaves this formulation as the object of conjectural interest.

References

Primary source

Simon Špacapan, “A note on Vizing's conjecture”, arXiv:2212.09571 (2022).

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.