Equality characterization for independent distance domination in connected bipartite graphs

Let d2d\geq 2, and let GG be a connected bipartite graph of order nn. Write C2d+2C_{2d+2} for the cycle of length 2d+22d+2, and let Bd\mathcal{B}_d denote the graph family defined in the source. The invariant γd1(G)\gamma_d^1(G) is the minimum size of a dd-distance dominating independent set in GG. The bipartite equality conjecture.

γd1(G)=nd+1G{C2d+2}Bd  or  n=d+1.\gamma_d^1(G)=\frac{n}{d+1}\quad\Longleftrightarrow\quad G\in\{C_{2d+2}\}\cup\mathcal{B}_d\ \text{ or }\ n=d+1.

This conjecture seeks a complete characterization of equality in the upper bound for connected bipartite graphs. The supplied source recalls the corresponding characterization for d=1d=1, while the asserted case d2d\geq 2 is posed as open.

Sources & referencesView supporting material

Primary source

Csilla Bujtás, Vesna Iršič Chenoweth, Sandi Klavžar and Gang Zhang, “Revisiting d-distance (independent) domination in trees and in bipartite graphs”, arXiv:2508.12804 (2025).

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.