CS Paper Radar

A Counterexample to Teschner's Bondage-Number Conjecture

Yousof Yavari

cs.DM math.CO ·submitted 2026-09-01 19:57 UTC · v1
theory

Abstract

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 $γ(G)$. Teschner conjectured that $b(G)\le \tfrac32Δ(G)$ for every graph $G$. We disprove this conjecture by giving a connected cubic bipartite graph on eighteen vertices with \[ γ(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.

Comment
9 pages, no figures; complete Python 3 verifier included in the appendix

Closest papers

Nearest neighbours by meaning across the whole index.

Domination versus edge domination in regular graphs of degree at least seven

cs.DM math.CO ·2026-08-23 ·Chakshu Gupta
similarity 0.76
Abstract · 15 pages, 1 table

Baste et al. (2020) conjectured that every regular graph of positive degree has domination number at most its edge domination number, the least size of a maximal matching. Combining published bounds settles the inequality for every degree at least nine. A reduction proves the inequality whenever one endpoint of each edge of a minimum maximal matching can be chosen to form a dominating set, and the Lovász Local Lemma shows such a choice exists for every degree at least seven, newly closing degrees seven and eight and leaving degrees three through six open. The reduction settles each open degree up to a bounded number of vertices, forty-eight for cubic graphs. At fifty vertices, however, the reduction meets an explicit cubic graph it cannot settle, though the inequality holds there too. The inequality cannot be tightened, since infinitely many cubic graphs have equal domination and edge domination numbers. The cubic case stays open, and even linear arguments from the local structure cannot close it. The middle degrees stay open beyond the graphs already settled.

0.34

Near-Optimal Distributed Domination in Planar Graphs

cs.DS cs.DC ·2026-09-26 ·Wojciech Wawrzyniak
theoryhighly cited similarity 0.71
Abstract · 19 pages, 7 figures

We give a deterministic $(8+\varepsilon)$-approximation for minimum dominating set on planar graphs in a constant number of rounds of the LOCAL model, for every $\varepsilon>0$. This improves the previous ratio $11+\varepsilon$ obtained by Heydt et al. The ratio is near-optimal in this model: its leading constant is only one above the known lower bound of $7$. Our result closes three quarters of the previous gap, reducing it from $4$ to $1$. Our main contribution is a sharp structural bound. For any dominating set $D$, assigning each vertex outside $D$ to a neighboring center gives disjoint owner blocks. If $k_x$ counts the other blocks containing a neighbor of $x$, then $\sum_{x\notin D}(k_x-2)^+\le(4|D|-12)^+$, where $z^+=\max\{z,0\}$. The bound holds for every such assignment, and equality holds for arbitrarily large minimum dominating sets. We use this bound in their three-phase framework, with new parameters and the same final linear-programming procedure. The algorithm requires neither a planar embedding nor the graph size, and its round bound depends only on $\varepsilon$. The transfer theorem of Bonamy et al. also gives a deterministic $(25+\varepsilon)$-approximation on graphs of bounded Euler genus, with a round bound depending only on $\varepsilon$ and the genus.

0.36

A Fine-Grained Complexity of Co-Secure Domination for Some Subclasses of Chordal Graphs

cs.DM ·2026-08-11 ·Manjusha M S, Renjith P
similarity 0.68
Abstract

For a connected graph $G = (V, E)$, a set $D \subseteq V$ is a co-secure dominating set if $D$ is a dominating set of $G$ and for each vertex $u \in D$ there exists a vertex $v \in V \setminus D$ such that $uv \in E$ and $(D \setminus \{u\}) \cup \{v\}$ is a dominating set of $G$. In this article, we present bounds on the co-secure domination number (size of minimum co-secure dominating set) in some restricted 2-trees, a popular subclass of chordal graphs. We also show an interesting dichotomy that the co-secure dominating set problem is NP-complete on $K_{1,r}$-free split graphs, $r\ge 4$, whereas it is linear-time solvable on $K_{1,3}$-free split graphs.

0.04

Clique Number of Tournaments II

cs.DM math.CO ·2026-09-07 ·Guillaume Aubian, Samuel Coulomb
theory similarity 0.66
Abstract

The directed clique number $\vecω(T)$ of a tournament $T$ is the minimum, over all orderings of the vertices of $T$, of the clique number of the graph whose edges are the arcs that point backward with respect to the ordering. In this paper, we prove that, for every integer $k \geq 3$, deciding whether $\vecω(T) \leq k$ is NP-complete. This answers a question of Nguyen, Scott, and Seymour, and contrasts with the classical undirected setting, where deciding whether $ω(G) \leq k$ is polynomial-time solvable for every fixed integer $k$. On the other hand, we give a polynomial-time algorithm distinguishing tournaments with $\vecω(T) \leq 2$ from those with $\vecω(T) > 100$. We also study the tournament analogue of the Gyárfás--Sumner conjecture. We construct new $\vecχ$-bounding tournaments and thereby prove a conjecture of Aboulker, Aubian, Charbit, and Lopes stating that every class of tournaments with bounded twin-width is $\vecχ$-bounded. We then exhibit new tournaments that are not $\vecχ$-bounding, disproving another conjecture of Aboulker, Aubian, Charbit, and Lopes, as well as two conjectures of Kim. Finally, we present infinite families of 3-$\vecω$-critical and 4-$\vecω$-critical tournaments.

0.06

Clique counts under degree and matching constraints

cs.DM math.CO ·2026-10-31 ·Rajat Adak
theory similarity 0.66
Abstract

We study the maximum number of $t$-cliques in graphs with maximum degree at most $D$ and matching number at most $M$, with no restriction on the number of vertices. For $t\ge 3$, we determine this maximum whenever $D\ge 2M-1$ and characterize all extremal graphs when the maximum is positive. Up to isolated vertices, these are complete or complete split graphs for $D\ge 2M$, while $K_{2M}$ is uniquely extremal when $D=2M-1$. We also derive a general upper bound from the Chvátal-Hanson edge theorem and refine it for even $D$. For fixed even $D$ and $3\le t\le D+1$, every extremal graph consists, apart from isolated vertices, of copies of $K_{D+1}$ together with a remainder whose order is bounded independently of $M$. When $D/2$ divides $M$, this remainder is empty and the extremal graph is unique. This structure yields an eventual recurrence, reducing the determination of all extremal values and graphs to finitely many matching bounds.

0.28

A Linear Kernel for Planar Semitotal Domination

cs.DS ·2026-10-27 ·Paloma T. de Lima, Lukas Retschmeier
similarity 0.66
Abstract

A set of vertices $S$ in a graph $G$ is a semitotal dominating set if $S$ is a dominating set and every vertex in $S$ has a witness, that is, another vertex in $S$ within distance at most two. The Semitotal Domination problem asks whether $G$ admits such a set of size at most $k$. We study this problem parameterized by the solution size. We provide a linear kernel of size $358k$ on planar graphs, a result that adds to several existing linear kernels for other domination variants on planar graphs. Additionally, we show Semitotal Domination is $W[2]$-hard on split graphs, on bipartite graphs and on $t$-claw-free graphs, it is $W[1]$-hard on circle graphs.

0.15

What remains of the planar induced minor conjectures?

cs.DM cs.CCcs.DSmath.CO ·2026-11-06 ·Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk, Paweł Rzążewski
similarity 0.64
Abstract · 26 pages, 7 figures

Dallard, Milanič, and Štorgel, and independently Gartland and Lokshtanov, conjectured that for every planar graph $H$, Maximum Weight Independent Set and List $3$-Coloring are polynomial-time solvable in $H$-induced-minor-free graphs. As a structural explanation, Gartland and Lokshtanov further conjectured that such graphs admit balanced separators dominated by a constant number of vertices. Bonnet and Chang recently refuted the independent-set part of the algorithmic conjecture, by showing that Maximum Independent Set is $\mathsf{NP}$-hard in graphs excluding the $5\times5$ grid as an induced minor. We revisit both conjectures. We show that the graphs used by Bonnet and Chang exclude much simpler planar graphs, including several $16$-vertex trees, and we introduce a second, independent family of hard instances. We also prove that $3$-Coloring is $\mathsf{NP}$-hard in both settings, thus refuting the algorithmic conjecture in full, even in its quasipolynomial version, unless $\mathsf{NP}\subseteq\mathsf{QP}$. On the structural side, we identify planar graphs $H$ for which the structural conjecture holds, while the algorithmic one fails. Thus, constantly dominated balanced separators cannot by themselves explain the tractability of Maximum Weight Independent Set and List $3$-Coloring.

0.15

Order 14 is the largest order for which every 4-total coloring of every cubic graph is equitable

cs.DM math.CO ·2026-09-04 ·Matheus Adauto, Celina de Figueiredo, Diana Sasaki, Rafael Schneider
similarity 0.63
Abstract

A total coloring of a graph is an assignment of colors to its vertices and edges so that adjacent or incident elements receive distinct colors, and it is equitable when the cardinalities of any two color classes differ by at most one. Stemock conjectured that every $4$-total coloring of a cubic graph of order less than $20$ is equitable. In this paper, we disprove this conjecture: the circular ladder $L_{12}$ admits a non-equitable $4$-total coloring and, moreover, no smaller counterexample exists: order $4$ is vacuous, and every $4$-total coloring of a cubic graph of order $6$, $8$, or $10$ is equitable. We also prove that the same property holds at order $14$. Our proofs rely on a decomposition lemma, which states that, in any $4$-total coloring of a cubic graph $G$, each color class consists of an independent set $S$ together with a perfect matching of $G-S$. We use the lemma to determine all possible color class configurations for orders $12$, $16$, and $18$, and we show that every listed configuration is attained. Finally, we provide a splicing construction showing that, for every even $n\geq16$, some connected cubic graph of order $n$ admits a non-equitable $4$-total coloring. We may conclude that $14$ is the largest order for which every $4$-total coloring of every cubic graph is equitable.

0.20