Paired Domination in Cubic Bipartite Graphs
En palabras de los autores
A paired dominating set of a graph is a dominating set such that has a perfect matching. The minimum size of such a set is the paired domination number . Desormeaux and Henning conjectured that every cubic bipartite graph of order satisfies . We prove the conjecture in the sharp integer form for every finite simple cubic bipartite graph . 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 the Gallai--Edmonds decomposition. Equality is attained by when and by the cube when .
Resultado principalEl resumen no menciona limitaciones.
Apareció: viernes, 25 de septiembre. arXiv. Preprint, todavía sin revisión por pares.