期刊
DISCRETE MATHEMATICS
卷 345, 期 9, 页码 -出版社
ELSEVIER
DOI: 10.1016/j.disc.2022.112967
关键词
PSD propagation time; PSD zero forcing; Migration; Nordhaus-Gaddum
类别
资金
- National Science Foundation
- NSF [2000037, 1916439]
- Simons Foundation [355645]
- Division Of Mathematical Sciences
- Direct For Mathematical & Physical Scien [2000037, 1916439] Funding Source: National Science Foundation
The paper establishes the upper bound for the positive semidefinite propagation time of a graph in terms of its positive semidefinite zero forcing number. Two methods and algorithms for transforming one positive semidefinite zero forcing set into another are presented to prove this bound. Consequences of the bound, including a tight Nordhaus-Gaddum sum upper bound on positive semidefinite propagation time, are established.
The tight upper bound pt+(G) < 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据