Counterexamples to five conjectures of Graffiti.pc on domination

Introduction

Graffiti.pc is a program written by DeLaViña in 2001 [4] after Fajtlowicz’s Graffiti [9]; it proposes inequalities between graph invariants that hold on its database of graphs. Its conjectures are collected, with their status, in DeLaViña’s list Written on the Wall II [5]. Several hundred of them concern total domination, and some have been settled [7, 6, 8]. This note disproves five conjectures that the list still marks as open:¹ four on total domination and one on independent domination. The proofs are by hand. As in [2], every finite statement is also re-checked by computer and in the Lean proof assistant; the computations are described in § 7 and Appendix § 8.

All graphs are finite, simple and connected. For a vertex $v$ of $G$, $N(v)$ is its set of neighbours and $N[v] = N(v) \cup\{v\}$; for $X \subseteq V(G)$, $N(X) = \bigcup_{v\in X} N(v)$ and $\langle X\rangle$ is the subgraph induced by $X$. A set $D$ is dominating if every vertex outside $D$ has a neighbour in $D$, and totally dominating if every vertex of $G$ has a neighbour in $D$. The domination number $\gamma(G)$ and the total domination number $\gamma_t(G)$ are the least sizes of such sets [3, 10]; the independent domination number $i(G)$ is the least size of a dominating set that is independent. A total dominating set is minimal if no proper subset is a total dominating set; since every superset of a total dominating set is one, this holds as soon as no single vertex can be removed. $G$ is well totally dominated if all its minimal total dominating sets have the same size [1]. A pendant vertex or leaf has degree one, and a support vertex is a neighbour of a leaf. We write $d(u,v)$ for the distance, $\operatorname{ecc}(v) = \max_u d(v,u)$ for the eccentricity, and $C(G)$ for the center, the set of vertices of least eccentricity. Following [5], the eccentricity of a set $X$ is

The number of vertices at even distance from $v$, including $v$ itself, is denoted $\operatorname{de}(v)$; the list calls it $\operatorname{disteven}(v)$. In a tree $T$, $L(T)$ is the set of leaves, $S(T)$ the set of support vertices, $D_2(T)$ the set of vertices of degree two, and $M(T)$ the set of vertices of maximum degree. Finally $\operatorname{iso}(H)$ and $c(H)$ are the numbers of isolated vertices and of components of a graph $H$.

The five conjectures read as follows in [5].

Corresponding author: [email protected]; ORCID 0000-0003-0466-750X.

Conjecture 352. If $T$ is a tree on $n>2$ vertices, then $\gamma_t(T)\ge c\langle N(D_2)\cup D_2\rangle+\left\lceil\frac{1}{2}\operatorname{ecc}_{\operatorname{avg}}(M)\right\rceil$, where $\operatorname{ecc}_{\operatorname{avg}}(M)$ is the average eccentricity of the vertices of maximum degree.

Conjecture 358. If $T$ is a tree on $n>2$ vertices, then $\gamma_t(T)\ge\frac{1}{2}\operatorname{ecc}(C)+\operatorname{iso}\langle S\rangle$.

Conjecture 359. If $T$ is a tree on $n>2$ vertices, then $\gamma_t(T)\ge\frac{1}{2}\operatorname{ecc}(C)+c\langle S\cup L\rangle$.

Conjecture 319. If $G$ has $n>1$ vertices and $\max_v\operatorname{de}(v)=\gamma(G)$, then $G$ is well totally dominated.

Conjecture 427. If $G$ has $n>3$ vertices, then $i(G)\le|E(C,V-C)|+\left\lfloor\frac{2}{3}|E\langle V-N(P)\rangle|\right\rfloor$, where $P$ is the set of pendant vertices, $E\langle X\rangle$ is the edge set of $\langle X\rangle$ and $E(C,V-C)$ the set of edges with exactly one end in $C$.

The printed statement of Conjecture 427 introduces the set $M$ of maximum-degree vertices and then uses the symbols $C$ and $P$ without defining them. In the neighbouring entries of the list, $C$ is the center (Conjectures 430a–c) and $P$ the set of pendant vertices (Conjecture 425d); we read the statement this way, and we show in Theorem 6.2 that it fails also if $C$ stands for $M$.

The smallest counterexamples are $T(3,4)$ with 18 vertices, $Q_3$ with 19, $G_3$ with 10, and an 8-vertex tree for Conjecture 427. An exhaustive search (§ 7) shows that $T(3,4)$ and $Q_3$ are the only counterexamples of their orders and that there are none smaller. Likewise $G_3$ is the only counterexample to Conjecture 319 with at most 11 vertices, and the 8-vertex tree the only counterexample to Conjecture 427 with at most 8 vertices.

Two tools

Proof. A leaf $\ell$ has the single neighbour $s$, so a total dominating set must contain $s$, and a dominating set must contain $\ell$ or $s$. $\square$

Proof. Each $q\in Q$ has a neighbour in $D$, which lies in $D\cap R$. Counting the pairs $(q,x)$ with $q\in Q$, $x\in D\cap R$ and $qx$ an edge gives $|Q|\le\sum_{x\in D\cap R}|N(x)\cap Q|\le2|D\cap R|$. $\square$

We also use Jordan’s theorem [11]: the center of a tree consists of the middle vertex, or the two middle vertices, of any longest path.

Conjecture 352

Proof. Write $T=T(a,r)$. The vertex $h$ has degree 4, the vertices $s_1,s_2,s_3$ have degree 3, the $x_i$ and $y_j$ have degree 2, and all other vertices are leaves. Hence $M=\{h\}$, and $\operatorname{ecc}(h)=d(h,z)=a+r+4$, since every other vertex is closer to $h$. As $a+r$ is odd, $\left\lceil\frac{1}{2}\operatorname{ecc}(h)\right\rceil=\frac{a+r+5}{2}$.

Next, $D_2=\{x_1,\ldots,x_a,y_1,\ldots,y_r\}$ and

The two sets on the right induce paths, and no edge joins them because $s_2$ lies in neither and $s_1s_3$ is not an edge. So $c\langle N(D_2)\cup D_2\rangle=2$, and the right side of Conjecture 352 equals $\frac{a+r+9}{2}$.

Upper bound. The set

has $5+\frac{a-3}{2}+\frac{r}{2}=\frac{a+r+7}{2}$ elements. It is a total dominating set: $h$ dominates its leaves and $x_1$; $x_1$ dominates $h$ and $x_2$; for $j\ge1$ the pair $x_{4j},x_{4j+1}$ dominates $x_{4j-1},\ldots,x_{4j+2}$, so that $x_1,\ldots,x_{a-1}$ are all dominated; $s_1$ dominates $x_a$, $\ell_1$ and $s_2$; $s_2$ dominates $s_1$, $s_3$ and $\ell_2$; $s_3$ dominates $s_2$, $\ell_3$ and $y_1$; and the pair $y_{4j-1},y_{4j}$ dominates $y_{4j-2},\ldots,y_{4j+1}$, where $y_{r+1}$ means $z$.

Lower bound. Let $D$ be any total dominating set. By Lemma 2.1, $h,s_1,s_2,s_3\in D$. Apply Lemma 2.2 to $R_1=N(h)\cup\{x_2,\ldots,x_a\}$ and $Q_1=\{h,x_2,\ldots,x_{a-1}\}$: the neighbours of $h$ and of each $x_i$ with $2\le i\le a-1$ lie in $R_1$, and a vertex of $R_1$ is adjacent to at most two vertices of $Q_1$. Hence $|D\cap R_1|\ge\frac{a-1}{2}$. Likewise, with $R_2=\{y_1,\ldots,y_r,z\}$ and $Q_2=\{y_2,\ldots,y_r,z\}$, $|D\cap R_2|\ge\frac{r}{2}$. The sets $\{h,s_1,s_2,s_3\}$, $R_1$ and $R_2$ are disjoint, so $|D|\ge4+\frac{a-1}{2}+\frac{r}{2}=\frac{a+r+7}{2}$. $\square$

Conjectures 358 and 359

with one leaf attached to each $s_j$ and to each $s'_j$ (Figure 2). It has $7k-2$ vertices. We call $\{s_j,c_j,s'_j\}$ the $j$-th block.

Proof. The leaves are the $2k$ attached vertices, so $S=\{s_j,s'_j: 1\le j\le k\}$. Two support vertices are at distance at least 2 (they are separated by $c_j$ or by $u_j,w_j$), so $\langle S\rangle$ has no edges and $\operatorname{iso}\langle S\rangle=2k$; in $\langle S\cup L\rangle$ each support vertex is joined only to its own leaf, so $\operatorname{c}\langle S\cup L\rangle=2k$.

The spine has $2k+3(k-1)=5k-3$ edges, and every vertex lies on the spine or is a leaf attached to it; the spine ends $s_1$ and $s'_k$ carry leaves. So the path from the leaf at $s_1$ to the leaf at $s'_k$, of length $5k-1$, is a longest path. Since $k$ is odd, $5k-1$ is even, and by Jordan’s theorem $C$ is the single vertex at distance $\frac{5k-1}{2}$ from both ends; this is $c_m$ with $m=\frac{k+1}{2}$, because the leaf at $s_1$ is at distance $1+5(m-1)+1=\frac{5k-1}{2}$ from $c_m$. Thus $\operatorname{ecc}(C)=\operatorname{ecc}(c_m)=\frac{5k-1}{2}$.

The set $B$ of all $3k$ block vertices is a total dominating set: each leaf is dominated by its support vertex, $s_j$ and $s'_j$ by $c_j$, $c_j$ by $s_j$, $u_j$ by $s'_j$, and $w_j$ by $s_{j+1}$. Conversely, let $D$ be a total dominating set. By Lemma 2.1, $S\subseteq D$. For each $j$ the vertices $s_j,s'_j$ need neighbours in $D$, and these lie in $X_j=N(s_j)\cup N(s'_j)$, which contains no support vertex. The sets $X_1,\ldots,X_k$ are pairwise disjoint, because each vertex outside $S$ is adjacent to support vertices of only one block: $c_j$ to $s_j,s'_j$; $u_j$ to $s'_j$; $w_j$ to $s_{j+1}$; a leaf to its support vertex. Hence $|D|\ge2k+k=3k$, and $\gamma_t(Q_k)=3k$.

Finally $\frac{1}{2}\operatorname{ecc}(C)+2k=\frac{5k-1}{4}+2k=3k+\frac{k-1}{4}$.

Conjecture 319

Remark 4.3. For even $k\ge4$ the center of $Q_k$ is the edge $u_{k/2}w_{k/2}$, $\operatorname{ecc}(C)=\frac{5k-2}{2}$, and the same argument gives right sides $3k+\frac{k-2}{4}>3k=\gamma_t(Q_k)$. For $k=2$ the two sides are equal.

Definition 5.1. For $k\ge3$ let $G_k$ consist of a complete graph on $c_1,\ldots,c_k$, a vertex $x$, and for each $i$ a path $x,p_i,q_i,c_i$ (Figure 3). It has $3k+1$ vertices.

Theorem 5.2. For $k\ge3$, every vertex $v$ of $G_k$ has $\operatorname{de}(v)=k+1$, and $\gamma(G_k)=\gamma_t(G_k)=k+1$. The sets $\{x,p_1,c_2,\ldots,c_k\}$ and $\{p_1,\ldots,p_k,q_1,\ldots,q_k\}$ are minimal total dominating sets of sizes $k+1$ and $2k$. Hence $G_k$ satisfies the hypothesis of Conjecture 319 and is not well totally dominated.

Proof. Distances. Let $i\ne j$. The following lists, read off from the paths through $x$ and through the clique, give the vertices at distance 1, 2 and 3; no distance exceeds 3.

vertex	distance 1	distance 2	distance 3	de
$x$	$p_i$	$q_i$	$c_i$	$1+k$
$p_i$	$x$, $q_i$	$p_j$, $c_i$	$q_j$, $c_j$	$1+(k-1)+1$
$q_i$	$p_i$, $c_i$	$x$, $c_j$	$p_j$, $q_j$	$1+1+(k-1)$
$c_i$	$c_j$, $q_i$	$p_i$, $q_j$	$x$, $p_j$	$1+1+(k-1)$

For instance $d(p_i,c_j)=3$ along $p_i,q_i,c_i,c_j$, while the route through $x$ has length 4; and $d(q_i,q_j)=3$ along $q_i,c_i,c_j,q_j$. In every row $\operatorname{de}=k+1$.

Domination. The $k$ sets $N[q_i]=\{p_i,q_i,c_i\}$ are disjoint, so a dominating set $D$ has at least $k$ vertices. Suppose $|D|=k$. Then $D$ has exactly one vertex in each $N[q_i]$ and does not contain $x$, so $x$ is dominated by some $p_i\in D$. Then $c_i\notin D$ and $q_i\notin D$, so $c_i$ is dominated by some $c_j\in D$, $j\ne i$. But then $p_j,q_j\notin D$ and $x\notin D$, so $p_j$ is not dominated, a contradiction. Hence $\gamma(G_k)\ge k+1$.

The set $A=\{x,p_1,c_2,\ldots,c_k\}$ is a total dominating set: $x$ is dominated by $p_1$; every $p_i$ by $x$; $q_1$ by $p_1$; $q_i$ by $c_i$ for $i\ge2$; $c_1$ by $c_2$; and $c_i$, $i\ge2$, by another $c_j$ with $j\ge2$, which exists since $k\ge3$. As $\gamma\le\gamma_t\le|A|=k+1$, we get $\gamma(G_k)=\gamma_t(G_k)=k+1$, and $A$ is minimal because it has the least possible size.

The set $B=\{p_1,\ldots,p_k,q_1,\ldots,q_k\}$ is a total dominating set: $x$ is dominated by $p_1$, $p_i$ and $q_i$ by each other, and $c_i$ by $q_i$. It is minimal: without $p_i$ the vertex $q_i$ has no neighbour in $B$, since $N(q_i)=\{p_i,c_i\}$; without $q_i$ the vertex $c_i$ has none, since $N(c_i)=\{q_i\}\cup\{c_j:j\ne i\}$. As $2k>k+1$, $G_k$ is not well totally dominated, while $\max_v\operatorname{de}(v)=k+1=\gamma(G_k)$. □

Remark 5.3. If $v$ itself is not counted in $\operatorname{dist}_{\mathrm{even}}(v)$, Conjecture 319 already fails for the path $v_1v_2v_3v_4v_5$: the largest count is $2=\gamma(P_5)$, while $\{v_2,v_3,v_4\}$ and $\{v_1,v_2,v_4,v_5\}$ are minimal total dominating sets. So the conjecture is false under either reading; the definition in [5] counts all vertices at even distance, which includes $v$.

Conjecture 427

Proof. In $H_m$ the path $\ell_{-m},v_{-m},\ldots,v_m,\ell_m$ is a longest path, so $C=\{v_0\}$ by Jordan’s theorem. As $v_0$ has degree 2, $|E(C,V-C)|=2$. The pendant vertices are the $\ell_j$, so $N(P)=\{v_j:j\ne0\}$ and $V-N(P)=\{v_0\}\cup\{\ell_j\}$, an independent set; the second term vanishes and the right side is 2. By Lemma 2.1 an independent dominating set meets each of the $2m$ disjoint sets $\{v_j,\ell_j\}$, $j\ne0$, so $i(H_m)\ge2m$; and $\{v_j:j\text{ odd}\}\cup\{\ell_j:j\ne0\text{ even}\}$ is an independent dominating set of size $2m$ (it dominates $v_0$ through $v_{\pm1}$).

In $F_m$ the vertex $v_2$ has degree 4 and every other vertex has degree at most 3, so $M=\{v_2\}$ and $|E(M,V-M)|=4$. Every spine vertex is a support vertex, so $V-N(P)$ is the set of leaves, which is independent; the right side is 4. By Lemma 2.1, $i(F_m)\ge m$, and the vertices $v_j$ with $j$ even together with the leaves at the $v_j$ with $j$ odd form an independent dominating set of size $m. □

The smallest counterexample has 8 vertices: the path $a_1a_2\cdots a_7$ with a leaf $b$ attached to $a_5$ (Figure 4(a)). The path $a_1\cdots a_7$ is a longest path, so the center is $\{a_4\}$, which has degree 2. The pendant vertices are $a_1$, $a_7$ and $b$, so $N(P)=\{a_2,a_5,a_6\}$, and $\langle V-N(P)\rangle$ has the single edge $a_3a_4$. The right side is $2+\lfloor\frac{2}{3}\rfloor=2$. On the other hand $N[a_5]$ has four vertices and every other closed neighbourhood at most three, so two vertices dominate at most seven of the eight vertices; and $\{a_2,a_5,a_7\}$ is an independent dominating set. So $i=3$.

Exhaustive search

The trees with at most 24 vertices (63,242,254 trees with 3 to 24 vertices) were generated with gentreeg from nauty [12], which implements the algorithm of Wright, Richmond, Odlyzko and McKay [13], and tested against Conjectures 352, 358 and 359; $\gamma_t$ was computed by a dynamic programme over a rooted tree, and compared with a brute-force computation for all trees with at most 16 vertices. Table 1 gives the numbers of counterexamples. The connected graphs were generated with geng. Among the 1,018,690,328 connected graphs with 2 to 11 vertices, 46 satisfy the hypothesis of Conjecture 319, and $G_3$ is the only one of them that is not well totally dominated. Among the 11,989,760 connected graphs with 4 to 10 vertices, Conjecture 427 has 1, 12 and 72 counterexamples with 8, 9 and 10 vertices and none smaller; with $C$ read as $M$ it has 5, all with 10 vertices.

$n$	trees	Conjecture 352	Conjectures 358, 359
3–17	81,135	0	0
18	123,867	1	0
19	317,955	4	1
20	823,065	13	3
21	2,144,505	31	14
22	5,623,756	73	38
23	14,828,074	157	108
24	39,299,897	318	255

Verification

The proofs above use no computation. The computer checks the finite claims about the smallest members of each family and the searches of § 7, independently in four languages; all files are in the repository listed under Data and code availability.

1. C. Exhaustive searches: search352.c and search358.c over trees in graph6 format (total domination number by dynamic programming, optionally compared with brute force over all vertex subsets), c319.c and c427.c over connected graphs (all parameters by exhaustion over vertex subsets, in integer arithmetic). The search for Conjecture 319 on the 1,006,700,565 connected graphs with 11 vertices was split into three parts with geng’s res/mod option.

2. Python (exact integer and rational arithmetic): for $T(a,r)$ with $a \in\{3,7,11\}$, $r \in\{4,8,12,16\}$, for $Q_k$ with odd $k \le11$, for $G_k$ with $k \le5$, for $H_m$ with $m \le5$ and for $F_m$ with $5 \le m \le8$, recomputes every quantity in Theorems 3.2–6.2 from the edge lists, and checks the stated values of $\gamma_t$, $\gamma$ and $i$ by exhaustion for the smaller members.

3. Julia: the same quantities, with $\gamma_t$, $\gamma$, $i$ and the minimal total dominating sets found by brute force over all vertex subsets (up to $2^{26}$ subsets), except that $\gamma_t(Q_k)$ for $k \ge5$ is computed by a tree dynamic programme.

4. Lean 4: self-contained files without Mathlib. For $T(3,4)$, $Q_3$, $G_3$, the 8-vertex tree and $F_5$ they compute the right sides of the conjectures from the edge lists and prove that the conjectures fail. The refutations of Conjectures 352, 358 and 359 exhibit a total dominating set that is too small and depend on no axioms; those of Conjectures 319 and 427 evaluate $\gamma$ and $i$ over all vertex subsets in the kernel and depend only on propext. The exact values $\gamma_t(T(3,4)) = 7$ and $\gamma_t(Q_3) = 9$ are also checked, by compiled evaluation (native_decide); the refutations do not use them.

Statements and Declarations

Funding

Funding. No funding was received for conducting this study.

Competing interests

Competing interests. The author has no competing interests to declare that are relevant to the content of this article.

Data and code availability

The programs, their outputs and the Lean files are available at https://github.com/creelie/eCY and archived on Zenodo, https://doi.org/10.5281/zenodo.23252219.

Use of generative AI

The author used Claude (Anthropic) for programming, computation and drafting; the author checked the mathematics and takes full responsibility for the content.

Formerly, Electro-Gravitational Space Propulsion Laboratory (EGSPL), Bhubaneswar, Odisha 751030, India

Email address: [email protected]

Email address: [email protected]

URL: https://orcid.org/0000-0003-0466-750X