Report
Upper Bounds for Positive Semidefinite Propagation Time
| العنوان: | Upper Bounds for Positive Semidefinite Propagation Time |
|---|---|
| المؤلفون: | Hogben, Leslie, Hunnell, Mark, Liu, Kevin, Schuerger, Houston, Small, Ben, Zhang, Yaqi |
| سنة النشر: | 2021 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics |
| الوصف: | The tight upper bound $\operatorname{pt}_+(G) \leq \left\lceil \frac{\left\vert \operatorname{V}(G) \right\vert - \operatorname{Z}_+(G)}{2} \right\rceil$ 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. Comment: 14 pages, 7 figures |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2111.12240 |
| رقم الانضمام: | edsarx.2111.12240 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |