Skip to content
Preprint

Paired Domination in Cubic Bipartite Graphs

Sep 2026 · 0 citations · 21 references
Mathematics

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)\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 the Gallai--Edmonds decomposition. Equality is attained by $K_{3,3}$ when $|V(G)|\equiv2\pmod4$ and by the cube $Q_3$ when $|V(G)|\equiv0\pmod4$.

View source

Similar papers

Preprint Sep 2026

An improved upper bound for the fair domination number of maximal outerplanar graphs

A dominating set $D$ of a graph $G$ is a \emph{fair dominating set} if every two vertices outside $D$ have the same number of neighbors in $D$, and the \emph{fair domination number} $\mathrm{fd}(G)$ is the minimum cardinality of such a set. Caro, Hansberg and Henning, who introduced this parameter, proved that $\mathrm...

Y. Caro, R. Škrekovski · 0 citations
Open access Sep 2026

Double Total Domination Number of Some Families of Graphs

Let $G$ be a graph of minimum degree at least two. A set $D \subseteq V(G)$ is said to be a \emph{double total dominating set} of $G$, for every vertex $v\in V (G) $ contains at least two neighbors in $D$. The minimum cardinality among all double total dominating sets of $G$ is the \emph{double total domination number}...

Srinu Irugula, P. Francis · 0 citations
Preprint Oct 2026

Counting cographs in locally dense graphs

An $n$-vertex graph $G$ is $(\rho, d)$-dense if for all $U \subseteq V(G)$ of size at least $\rho n$, the induced subgraph $G[U]$ contains at least $\frac{d}{2}|U|^2$ edges. In 2010, partly motivated by the theory of quasirandomness, Kohayakawa, Nagle, R\"{o}dl, and Schacht conjectured that, for any fixed graph $F$, th...

Hyunwoo Lee · 0 citations
Review Sep 2026

Long Cycles in 2-Connected Tough Graphs

Let $G$ be a graph. The circumference of $G$, denoted by $cir(G)$, is the length of a longest cycle in $G$, or zero if $G$ is acyclic. In 1993, Broersma, van den Heuvel, Jung, and Veldman conjectured that, for every $t>0$, there is a constant $A=A(t)>0$ such that every 2-connected $t$-tough graph of order $n$ has circu...

Songling Shan · 1 citation
Preprint Sep 2026

Removable matchings in $2$-connected graphs

A matching $M$ of a $2$-connected graph $G$ is removable if $G-M$ is $2$-connected, extending Halin's classical notion of a removable edge. We prove that for every integer $d\ge 5$, every $2$-connected graph $G$ with $\delta(G)\ge d$ and $|V(G)|\ge 2d$ has a removable $d$-matching. This is best possible, since the comp...

Ringi Kim · 0 citations
Preprint Sep 2026

Rainbow connecting $2$-colorings of super-Dirac graphs

Let $G$ be a graph with minimum degree $\delta(G)\ge|V(G)|/2$. Can we color the edges of $G$ with red and blue so that every pair of non-adjacent vertices is connected by a path consisting of exactly one red edge and one blue edge? We provide an affirmative answer to this question for a class of graphs that are ``close...

J'anos Bar'at, Simona Boyadzhiyska, Andrea Freschi · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.