For a finite simple graph $G$ with at least one edge, the bondage number $b(G)$ is the least number of edges whose deletion increases the domination number $\gamma(G)$. Teschner conjectured that $b(G)\le \tfrac32\Delta(G)$ for every graph $G$. We disprove this conjecture by giving a connected cubic bipartite graph on eighteen vertices with \[ \gamma(G)=6 \qquad\text{and}\qquad b(G)=5. \] The domination number is established by a complete counting argument across the bipartition. An explicit five-edge deletion raises the domination number from six to seven. For the matching lower bound, we give an exact finite certificate: the graph has 297 minimum dominating sets, and deleting any one of its $\binom{27}{4}=17{,}550$ four-edge subsets leaves at least one of those sets dominating. The enumeration is deterministic, uses only exact integer and set operations, and is reproduced by the complete standard-library verifier included in the appendix.
Let $\mathcal{B}$ be the class consisting of the six-vertex bipartite graphs that possess a perfect matching and their complements. It is proved that every $\mathcal{B}$-free graph $G$ satisfies $\alpha(G)+\omega(G)\ge |V(G)|-1$. This establishes Conjecture 3.1 of Litjens, Polak and Sivaraman (B-Free Graphs Conjecture)...
The toughness of a connected noncomplete graph $G$ is$$\tau(G)=\min\left\{\frac{|S|}{c(G-S)}:S\subseteq V(G),\ c(G-S)\geq2\right\},$$where $c(G)$ is the number of components of $G$; as usual, $\tau(K_n)=\infty$. In 1973, Bondy proposed the metaconjecture that almost every nontrivial condition implying Hamiltonicity sho...
Cai-Li Jia, Xiang-Ge Liu, Lu Yong et al.· Electronic Journal of Combin...· 0 citations
The total domination number $\gamma_t(G)$ of a graph $G$ is the minimum cardinality of a set $D\subseteq V(G)$ such that every vertex of $G$ has a neighbor in $D$. The annihilation number $a(G)$ is the largest integer $k$ for which the sum of the $k$ smallest degrees of $G$ is at most $|E(G)|$. A well-known conjecture,...
Let $\nu(G)$ be the maximum number of edge-disjoint triangles in a graph $G$ and $\tau(G)$ the minimum number of edges meeting every triangle. Tuza conjectured that $\tau(G)\le 2\nu(G)$. We prove that $\tau(G)\le (165/59)\nu(G)$. The constant $165/59\approx 2.797$ improves the bound $66/23\approx 2.870$ that Haxell pro...
We study the complementary version of Hedetniemi's problem for infinite graphs. We prove that if a graph $G$ and its complement $\overline{G}$ are both uncountably chromatic while their categorical product is countably chromatic, then $|V(G)|=\omega_1$. Assuming $\diamondsuit$, we construct a graph $G$ on $\omega_1$ su...
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 th...
Chang-Hong Lu, Qi Wu· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
