Hamid's independent transversal domination bound for connected graphs

At least 8 years old · documented by

Let GG be a non-complete connected graph on nn vertices. For a graph GG, an independent transversal dominating set is a dominating set S⊆V(G)S\subseteq V(G) such that S∩I≠∅S\cap I\neq\emptyset for every maximum independent set I∈Ω(G)I\in\Omega(G); let γit(G)\gamma_{it}(G) denote the minimum cardinality of such a set. Hamid's conjecture.

γit(G)≤⌈n2⌉.\gamma_{it}(G)\leq\left\lceil\frac{n}{2}\right\rceil.

The preceding theorem establishes the bound when α(G)≥n/2\alpha(G)\geq n/2; the paper states that this conjecture is not true in general.

References

Primary source

Hongting Wang, Baoyindureng Wu and Xinhui An, “Independent transversal domination number of a graph”, arXiv:1704.06093 (2017).

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.