Nowakowski's independent domination conjecture for categorical graph products

Let GG and HH be graphs, and let i(G)i(G) denote the smallest cardinality of an independent dominating set in GG, equivalently the cardinality of a smallest maximal independent set. Nowakowski's conjecture. For all graphs GG and HH,

i(G×H)i(G)i(H).i(G\times H)\geq i(G)\cdot i(H).

This conjecture asks whether the independent domination number is supermultiplicative under the categorical product. It is cited in the source as an existing conjecture, and no resolution status is supplied.

Sources & referencesView supporting material

Primary source

Wing-Kai Hon, Ton Kloks, Hsiang-Hsuan Liu, Sheung-Hung Poon and Yue-Li Wang, “Results on independent sets in categorical products of graphs, the ultimate categorical independence ratio and the ultimate categorical independent domination ratio”, arXiv:1306.1656 (2013).

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.