Zero Forcing on 2-connected Outerplanar Graphs

NEW

Problem: Reconstructed statement: for finite simple undirected graphs, with $n=|V(G)|$ and $Z(G)$ the standard zero forcing number, ask whether there are absolute constants $\alpha<1$ and $k$ such that

$$Z(G)\le \alpha n+k$$

for every $G$ in each of the following planar families: maximal planar graphs, 3-connected planar graphs, and planar 3-trees. I interpret the question as asking for one uniform linear bound away from $n$; the proof below gives one for all planar graphs of minimum degree at least $3$, hence for all three listed families up to harmless small degeneracies.

Result: Yes. Let

$$c=\frac1{72}\left(\frac{35}{36}\right)^{35}>0,\qquad \alpha=1-c<1.$$

Then every finite simple planar graph $G$ with $\delta(G)\ge 3$ satisfies

$$Z(G)\le (1-c)n.$$

Thus the listed graph classes satisfy the desired bound; taking $k=1$ covers any nonstandard degenerate convention such as $K_1$.

Proof. Call a vertex high if $\deg v\ge 36$, and let $H$ be the set of high vertices. By Euler’s planar edge bound,

$$36|H|\le \sum_{v\in H}\deg v\le 2|E(G)|<6n,$$

so $|H|<n/6$.

Let $B$ be the set of vertices whose every neighbor is high. Put $X=B\setminus H$. Every $x\in X$ has degree at least $3$, all its neighbors lie in $H$, and the bipartite subgraph between $X$ and $H$ is planar. Hence

$$3|X|\le e(X,H)\le 2(|X|+|H|),$$

so $|X|\le 2|H|$. Therefore

$$|B|\le |H|+|X|\le 3|H|<n/2.$$

Thus at least $n/2$ vertices have a neighbor of degree at most $35$. For each such vertex $v$, choose one such neighbor $\ell(v)$.

Now choose a random set $R\subseteq V(G)$, including each vertex independently with probability $p=1/36$. Let $W$ be the set of vertices $v\notin B$ such that

$$v\in R,\qquad \ell(v)\notin R,\qquad (N(\ell(v))\setminus\{v\})\cap R=\varnothing .$$

For each $v\notin B$,

$$\Pr(v\in W)=p(1-p)^{\deg \ell(v)} \ge \frac1{36}\left(\frac{35}{36}\right)^{35}.$$

By linearity of expectation, some choice of $R$ gives

$$|W|\ge \frac n2\cdot \frac1{36}\left(\frac{35}{36}\right)^{35}=cn.$$

For every $w\in W$, the vertex $\ell(w)\notin W$ and has exactly one neighbor in $W$, namely $w$. Therefore $V(G)\setminus W$ is a zero forcing set: list the vertices of $W$ arbitrarily, and each $w$ is forced by $\ell(w)$ when its turn comes. Hence

$$Z(G)\le n-|W|\le (1-c)n.$$

Since every 3-connected planar graph has minimum degree at least $3$, every maximal planar graph with $n\ge4$ has minimum degree at least $3$, and every planar 3-tree has minimum degree at least $3$, the desired bound follows for all three families. Audit: the proof uses only finite simple planarity and $\delta(G)\ge3$; these hypotheses hold for the intended nondegenerate graph classes, and $k=1$ absorbs any exceptional small convention.

Citation: No prior resolution is used here. The proof is self-contained apart from the standard Euler planar and bipartite-planar edge bounds.