The lower-bound conjecture for secure domination in subdivisions

Let GG be a graph, and let G12G^{\frac{1}{2}} denote its 22-subdivision, obtained by replacing each edge with a path of length 22. Write γs(H)\gamma_s(H) for the secure domination number of a graph HH.

Secure-domination lower-bound conjecture. For every graph GG,

γs(G12)>45V(G).\gamma_s\left(G^{\frac{1}{2}}\right)>\frac{4}{5}|V(G)|.

The conjecture is motivated by examples showing that the secure domination number of a 22-subdivision can be smaller than both the number of edges and the number of vertices of the original graph; its status is not established in the supplied source.

Sources & referencesView supporting material

Primary source

Nima Ghanbari, “Secure domination number of k-subdivision of graphs”, arXiv:2110.09190 (2023).

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.