Upper bounds for positive semidefinite propagation time

DOI10.1016/J.DISC.2022.112967zbMATH Open1491.05081arXiv2111.12240OpenAlexW3214820322MaRDI QIDQ2144516FDOQ2144516

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)

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.

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

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

zbMATH Keywords

migrationNordhaus-GaddumPSD propagation timePSD zero forcing

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• Throttling positive semidefinite zero forcing propagation time on graphs
• 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)