arXiv:2605.10836 · v2

The Path-Extremal Conjecture for Zero Forcing: Distance-Hereditary Graphs and a Split-Decomposition Reduction

零强制路径极值猜想：距离遗传图与分裂分解归约

首次提交 2026-05-12 00:51

版本更新 2026-11-13 01:36

雷达观测 2026-11-13 14:15

摘要

A zero-forcing set of a graph is a set for which, after regarding each of its vertices as being blue, and applying the rule that a blue vertex with exactly one white neighbor forces said neighbor to become blue, all of the vertices in the graph are blue. Let $z(G;k)$ denote the number of zero forcing sets of size $k$. A conjecture of Boyer et al.\ asserts that the path $P_n$ maximizes these numbers coefficientwise among all $n$-vertex graphs. We prove this path-extremal conjecture for distance-hereditary graphs, which is the class of all graphs $G$ such that for each of the connected induced subgraphs of $G$, the distances between any two vertices in that subgraph are the same as they are in $G$. This extends the previously known tree case in which the path-extremal conjecture was known to be true to a much larger class that includes, in particular, all trees and all cographs. We then use canonical split decomposition to push the argument we used to show the distance-hereditary result into the more general setting of a connected graph with at most one prime bag in its canonical split decomposition. Specifically, we show that if a split-prime graph $H$ and all of its induced subgraphs are path-extremal, then every connected graph whose canonical split decomposition has a unique prime bag whose label graph is isomorphic to $H$ is also path-extremal. As a corollary of this result, for each fixed $m$, if every induced subgraph of every split-prime graph on at most $m$ vertices is path-extremal, then so is every connected graph whose canonical split decomposition has a unique prime bag of size at most $m$. Additionally, we prove that the path-extremal conjecture holds when all prime bags have order at most six, without restricting their number; under the preceding hereditary hypothesis, one additional prime bag labelled by $H$ is also allowed.

作者备注：This version strengthens the split-decomposition reduction: it allows arbitrarily many prime bags of order at most six, together with at most one additional prime bag whose label graph has every induced subgraph path-extremal, whereas the previous version restricted the total number of prime bags to at most one, subject to the same condition on its label graph. Also streamlined the exposition

期刊信息：32nd International Computing and Combinatorics Conference (COCOON 2026), Lecture Notes in Computer Science, vol. 16835, pp. 409-422, Springer (2027)