Zero Forcing on Maximal Outerplanar Graphs: Capacities and Phase Repair
Abstract
We determine the zero-forcing number of maximal biconnected outerplanar graphs. When the weak dual is a path, the zero-forcing number and the induced path-covering number are both two. Otherwise, the branching faces determine a canonical core and a family of terminal strips. We prove that an optimal forcing process can be chosen in a normal form governed by explicit vertex and face capacities on the core. After fixing forests on the terminal strips, the zero-forcing number is expressed through an optimization over core-edge selections and the minimum number of root connections that must be removed to obtain an executable orientation. The path-covering number is obtained from the same capacity optimization without the repair cost. We characterize executable orientations by blocking-circuit equations and identify the two-path obstruction with a first cohomology class of a signed contact multigraph. Local replacements and a finite comparison of boundary recurrences establish the normal form for graphs of arbitrary size. A fifty-six-state recurrence constructs a minimum zero-forcing set and a complete forcing chronology in linear time from indexed triangle adjacency. We also obtain exact replacement results for rooted blocks and construct infinite families in which the zero-forcing number exceeds the path-covering number.
Related
- An improved upper bound for the fair domination number of maximal outerplanar graphs
- The minimum spectral radius of maximal outerplanar graphs
- On the fault-tolerant metric dimension of maximal outerplanar graphs
- Bounds for B-coloring planar and outerplanar graphs
- The scramble number of outerplanar graphs
BibTeX
@misc{han2026zero,
title = {{Zero Forcing on Maximal Outerplanar Graphs: Capacities and Phase Repair}},
author = {Zongjian Han and Yiran Liang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.31138},
eprint = {2610.31138},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.31138},
}
RIS
TY - UNPB
TI - Zero Forcing on Maximal Outerplanar Graphs: Capacities and Phase Repair
AU - Zongjian Han
AU - Yiran Liang
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2610.31138
UR - https://arxiv.org/abs/2610.31138
AB - We determine the zero-forcing number of maximal biconnected outerplanar graphs. When the weak dual is a path, the zero-forcing number and the induced path-covering number are both two. Otherwise, the branching faces determine a canonical core and a family of terminal strips. We prove that an optimal forcing process can be chosen in a normal form governed by explicit vertex and face capacities on the core. After fixing forests on the terminal strips, the zero-forcing number is expressed through an optimization over core-edge selections and the minimum number of root connections that must be removed to obtain an executable orientation. The path-covering number is obtained from the same capacity optimization without the repair cost. We characterize executable orientations by blocking-circuit equations and identify the two-path obstruction with a first cohomology class of a signed contact multigraph. Local replacements and a finite comparison of boundary recurrences establish the normal form for graphs of arbitrary size. A fifty-six-state recurrence constructs a minimum zero-forcing set and a complete forcing chronology in linear time from indexed triangle adjacency. We also obtain exact replacement results for rooted blocks and construct infinite families in which the zero-forcing number exceeds the path-covering number.
ER -