Zero Forcing on Maximal Outerplanar Graphs: Capacities and Phase Repair

Source 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.