Upper domination conjecture for direct products of complete multipartite graphs

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 2b1b2bt2\leq b_1\leq b_2\leq\cdots\leq b_t. The upper domination conjecture.

Γ(G)=1b1i=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 t3t\leq 3 but remains open in general. A particularly attractive unresolved special case is G=i=1tK3G=\prod_{i=1}^t K_3.

Sources & referencesView supporting material

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.