Packing and Covering Cycles Through Prescribed Vertices
Hanzhi Bai, Jin Yan
Source abstract
Let $G$ be a finite simple graph and let $S\subseteq V(G)$. We prove that the minimum number of vertices meeting every cycle that intersects $S$ is at most the maximum number of vertices of $S$ covered by a collection of vertex-disjoint cycles. This answers a question posed by Bowler, Ghorbani, Gut, Jacobs, and Reich [\emph{SIAM Journal on Discrete Mathematics} \textbf{40} (2026), 988--999]. An incidence-based reduction to their bidirected packing--covering theorem preserves the packing value and projects transversals without increasing their cardinality.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.