Upper domination conjecture for direct products of complete multipartite graphs

About 9 years old · traced to

Let K[ai,bi]K[a_i,b_i] denote the complete bib_i-partite graph with aia_i vertices in each part, and let GG be its direct product

G=∏i=1tK[ai,bi].G= \prod_{i=1}^t K[a_i,b_i].

Assume 2≤b1≤b2≤⋯≤bt2\leq b_1\leq b_2\leq\cdots\leq b_t. The upper domination conjecture.

Γ(G)=1b1∏i=1taibi.\Gamma(G)=\frac{1}{b_1}\prod_{i=1}^t a_i b_i.

Here Γ(G)\Gamma(G) is the maximum size of a minimal dominating set of GG. The proposition preceding the conjecture proves the corresponding lower bound, and the equality is known when t≤3t\leq 3 but remains open in general. A particularly attractive unresolved special case is G=∏i=1tK3G=\prod_{i=1}^t K_3.

References

Primary source

Colin Defant and Sumun Iyer, “Domination and Upper Domination of Direct Product Graphs”, arXiv:1708.01305 (2018).

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.