Skip to content
DraconiticResearch
Search Sources API
201,683 studies31 sourcesUpdated 53 min ago
PreprintarXiv licencearXiv

Paired Domination in Cubic Bipartite Graphs

  • Changhong Lu
  • Qi Wu
Open at sourcePDFDOICite

Abstract

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)≤ n/2. We prove the conjecture in the sharp integer form gpr(G)≤ 2⌊ |V(G)|/4⌋ 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 the Gallai--Edmonds decomposition. Equality is attained by K3,3 when |V(G)|≡2pmod4 and by the cube Q3 when |V(G)|≡0pmod4.

Related

  1. Roman Domination on Circular-Convex, Triad-Convex Bipartite Graphs and P4-Tidy Graphs
    Gautam K. Das, Kamal Santra
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. On $1$-limited and (1,2)-domination in cubic graphs
    Goran Radić, Aleksandra Tepeh
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Structural aspects of $1$-limited domination in cubic graphs
    Goran Radić, Gordana Radić, Aleksandra Tepeh
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. The domination number of the 2-token graph of the complete bipartite graph
    E. Acosta Troncoso, I. Caldera Caldera, L. M. Rivera
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. The domination number of the k-token graph of the complete bipartite graph Km,n
    Nathaniel Chinman, Antonio Cortijo, Beatrice Pedroni +2
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{lu2026paired,
  title = {{Paired Domination in Cubic Bipartite Graphs}},
  author = {Changhong Lu and Qi Wu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.30152},
  eprint = {2609.30152},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.30152},
}
RIS
TY  - UNPB
TI  - Paired Domination in Cubic Bipartite Graphs
AU  - Changhong Lu
AU  - Qi Wu
PY  - 2026
DA  - 2026/09/24
PB  - arXiv
DO  - 10.48550/arxiv.2609.30152
UR  - https://arxiv.org/abs/2609.30152
AB  - 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)≤ n/2. We prove the conjecture in the sharp integer form gpr(G)≤ 2⌊ |V(G)|/4⌋ 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 the Gallai--Edmonds decomposition. Equality is attained by K_3,3 when |V(G)|≡2pmod4 and by the cube Q_3 when |V(G)|≡0pmod4.
ER  -