Written on the Wall II - Conjecture 291

Reference: E. DeLaVina, Written on the Wall II, Conjectures of Graffiti.pc

Definitions

For a vertex $v$ in a graph $G$, $T(v)$ is the number of triangles (3-cliques) incident to $v$, i.e., the number of 3-element cliques in $G$ that contain $v$.

The triangle-frequency of the minimum is the number of vertices that achieve the minimum value of $T(v)$.

$k$ is the first step in the Havel–Hakimi process at which a zero appears. Concretely, starting from the descending degree sequence $s_0$ of $G$, we set $s_{i+1} = \mathrm{havelHakimiStep}\, s_i$ and let $k$ be the least $i \ge 0$ such that $s_i$ contains a zero entry (or, vacuously, has been emptied entirely). Since each step is sorted descending and never increases entries, this is equivalent to the last (smallest) entry of $s_i$ being $0$, or $s_i$ being $[]$.

This is strictly weaker than $n - \mathrm{residue}(G)$: $n - \mathrm{residue}(G)$ is the total number of reduction steps until every entry is zero, whereas $k$ only requires that some entry has hit zero — and a $0$ typically appears well before the all-zero state is reached.

Conjecture 291: For a simple connected graph $G$ with $n > 2$, $\gamma_t(G) \le k + \mathrm{frequency}(t_{\min}(v))$ where $\gamma_t(G)$ is the total domination number, $k$ is the Havel-Hakimi zero step, and $\mathrm{frequency}(t_{\min}(v))$ is the number of vertices achieving the minimum triangle count.

noncomputable def WrittenOnTheWallII.GraphConjecture291.minTrianglesAtVertex {α : Type u_1} [Fintype α] [DecidableEq α] [Nontrivial α] (G : SimpleGraph α) [DecidableRel G.Adj] : ℕ

The minimum number of triangles incident to any vertex, over all vertices of $G$.

Equations

• WrittenOnTheWallII.GraphConjecture291.minTrianglesAtVertex G = Finset.univ.inf' ⋯ G.numTrianglesAtVertex

noncomputable def WrittenOnTheWallII.GraphConjecture291.freqMinTriangles {α : Type u_1} [Fintype α] [DecidableEq α] [Nontrivial α] (G : SimpleGraph α) [DecidableRel G.Adj] : ℕ

The number of vertices achieving the minimum triangle count.

Equations

• WrittenOnTheWallII.GraphConjecture291.freqMinTriangles G = {v : α | G.numTrianglesAtVertex v = WrittenOnTheWallII.GraphConjecture291.minTrianglesAtVertex G}.card

noncomputable def WrittenOnTheWallII.GraphConjecture291.descDegreeSequence {α : Type u_1} [Fintype α] (G : SimpleGraph α) [DecidableRel G.Adj] : List ℕ

The descending degree sequence of $G$, used as the starting point of the Havel-Hakimi reduction.

Uses Finset.univ.val.map (multiset, duplicate-preserving) rather than Finset.univ.image (set, deduplicating), so that e.g. $C_4$ produces $[2, 2, 2, 2]$ rather than $[2]$.

Equations

• WrittenOnTheWallII.GraphConjecture291.descDegreeSequence G = (Multiset.map (fun (v : α) => G.degree v) Finset.univ.val).sort fun (x1 x2 : ℕ) => x1 ≥ x2

noncomputable def WrittenOnTheWallII.GraphConjecture291.havelHakimiIterate {α : Type u_1} [Fintype α] (G : SimpleGraph α) [DecidableRel G.Adj] (i : ℕ) : List ℕ

The Havel-Hakimi sequence of iterates: s i is the result of applying havelHakimiStep $i$ times to the descending degree sequence of $G$.

Equations

• WrittenOnTheWallII.GraphConjecture291.havelHakimiIterate G i = SimpleGraph.havelHakimiStep^[i] (WrittenOnTheWallII.GraphConjecture291.descDegreeSequence G)

noncomputable def WrittenOnTheWallII.GraphConjecture291.havelHakimiZeroStep {α : Type u_1} [Fintype α] (G : SimpleGraph α) [DecidableRel G.Adj] : ℕ

The first step $i$ (counting from $0$) at which a zero appears in the Havel-Hakimi reduction of the descending degree sequence of $G$, or in which the sequence has been emptied. We use sInf over the set of such $i$ so the definition is well-defined for every graph: in particular, when $G$ is a connected graph with $n \ge 2$ the minimum degree at iteration $0$ is at least $1$, so the first zero only appears at some $i \ge 1$; and since each step strictly shortens the list (or empties it), at the latest by $i = n$ the sequence is empty and the predicate holds vacuously.

This is the WOWII $k$ of Conjecture 291, which is the first step at which a zero appears — typically strictly less than $n - \mathrm{residue}(G)$ (which is the total number of reduction steps to reach the all-zero state).

Equations

• One or more equations did not get rendered due to their size.

theorem WrittenOnTheWallII.GraphConjecture291.conjecture291 {α : Type u_1} [Fintype α] [DecidableEq α] [Nontrivial α] (G : SimpleGraph α) [DecidableRel G.Adj] (h : G.Connected) (hn : 2 < Fintype.card α) : G.totalDominationNumber ≤ havelHakimiZeroStep G + freqMinTriangles G

WOWII Conjecture 291

For a simple connected graph $G$ with $n > 2$, $\gamma_t(G) \le k + \mathrm{frequency}(t_{\min}(v))$ where:

• $\gamma_t(G)$ is the total domination number,
• $k$ is the first step in which a zero appears in the Havel-Hakimi process,
• $\mathrm{frequency}(t_{\min}(v))$ is the number of vertices achieving the minimum triangle count.