Upper bounds for positive semidefinite propagation time

DOI10.1016/J.DISC.2022.112967MaRDI QIDQ2144516zbMATH OpenOpenAlexFDO

Authors Leslie Hogben, Mark Hunnell, Houston Schuerger, Ben Small, Kevin F. R. Liu, Yaqi Zhang

Publication date 14 June 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.12240

zbMATH Keywords

migrationNordhaus-GaddumPSD propagation timePSD zero forcing

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: The tight upper bound $operatorname{pt}_{+}(G)leqleftlceilfracleftvertoperatornameV(G)ightvert-operatorname{Z}_{+}(G)2ightceil$ is established for the positive semidefinite propagation time of a graph in terms of its positive semidefinite zero forcing number. To prove this bound, two methods of transforming one positive semidefinite zero forcing set into another and algorithms implementing these methods are presented. Consequences of the bound, including a tight Nordhaus-Gaddum sum upper bound on positive semidefinite propagation time, are established.

Recommendations

• Throttling positive semidefinite zero forcing propagation time on graphs
• Positive semidefinite propagation time
• Positive semidefinite zero forcing
• Bounds on expected propagation time of probabilistic zero forcing
• A new lower bound for positive zero forcing

Cites work

• Iteration index of a zero forcing set in a graph
• Positive semidefinite maximum nullity and zero forcing number
• Positive semidefinite propagation time
• Positive semidefinite zero forcing
• Propagation time for zero forcing on a graph
• Zero forcing parameters and minimum rank problems
• Zero forcing sets and the minimum rank of graphs

Cited in

(4)

• Throttling positive semidefinite zero forcing propagation time on graphs
• New structures and their applications to variants of zero forcing and propagation time
• Zero forcing propagation time intervals and graphs with fixed propagation time
• Positive semidefinite propagation time

This page was built for publication: Upper bounds for positive semidefinite propagation time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2144516)