A Characterization of Claw-Free Graphs using Zero Forcing Invariants

2024/12/04 by Randy Davila, Davila, Randy, Houston Schuerger +3 · 2 citations
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2412.03463

openalex publication_date 2024/12/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that the standard zero forcing number Z(G) and the positive semidefinite zero forcing number Z₊(G) are equal for all claw-free graphs G. This result resolves a conjecture proposed by the computer program TxGraffiti and highlights a connection between these graph invariants in claw-free structures. As a corollary, we show that a graph G is claw-free if and only if every induced subgraph H ⊆ G satisfies Z(H) = Z₊(H).

Cited by

• Zero forcing propagation time intervals and graphs with fixed propagation time
• In Reverie Together: Ten Years of Mathematical Discovery with a Machine Collaborator

Related

• Zero Forcing in Claw-Free Cubic Graphs
• Another conjecture of TxGraffiti concerning zero forcing and domination in graphs
• Computer assisted discovery: Zero forcing vs vertex cover
• Strongly Perfect Claw-free Graphs -- A Short Proof
• Loop zero forcing and grundy domination in planar graphs and claw-free cubic graphs