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

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

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

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,

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

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

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

For each $v\notin B$,

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

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

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.