{"id":"arxiv/2609.30152","url":"https://arxiv.org/abs/2609.30152","tags":["math.CO"],"score":0,"title":"Paired Domination in Cubic Bipartite Graphs","domain":"math.CO","source":"arxiv","authors":["Changhong Lu","Qi Wu"],"reviews":0,"subject":"math.CO","summary":"A paired dominating set of a graph $G$ is a dominating set $D$ such that $G[D]$ has a perfect matching. The minimum size of such a set is the paired domination number $\\gpr(G)$. Desormeaux and Henning conjectured that every cubic bipartite graph $G$ of order $n$ satisfies $\\gpr(G)\\le n/2$. We prove the conjecture in the sharp integer form $\\gpr(G)\\le 2\\lfloor |V(G)|/4\\rfloor$ for every finite simple cubic bipartite graph $G$. The proof combines a directed contraction along a perfect matching, switching arguments based on dominator trees, a four-symbol boundary calculus for two-edge cuts, and…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{}}