Deduction, Constrained Zero Forcing, and Constrained Searching
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929568599769088 |
|---|---|
| author | Burgess, Andrea Dyer, Danny Ojakian, Kerry Wang, Lusheng Xiao, Mingyu Yang, Boting |
| author_facet | Burgess, Andrea Dyer, Danny Ojakian, Kerry Wang, Lusheng Xiao, Mingyu Yang, Boting |
| contents | Deduction is a recently introduced graph searching process in which searchers clear the vertex set of a graph with one move each, with each searcher's movement determined by which of its neighbors are protected by other searchers. In this paper, we show that the minimum number of searchers required to clear the graph is the same in deduction as in constrained versions of other previously studied graph processes, namely zero forcing and fast-mixed search. We give a structural characterization, new bounds and a spectrum result on the number of searchers required. We consider the complexity of computing this parameter, giving an NP-completeness result for arbitrary graphs, and exhibiting families of graphs for which the parameter can be computed in polynomial time. We also describe properties of the deduction process related to the timing of searcher movement and the success of terminal layouts. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_22962 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Deduction, Constrained Zero Forcing, and Constrained Searching Burgess, Andrea Dyer, Danny Ojakian, Kerry Wang, Lusheng Xiao, Mingyu Yang, Boting Combinatorics Discrete Mathematics 05C57, 05C85 Deduction is a recently introduced graph searching process in which searchers clear the vertex set of a graph with one move each, with each searcher's movement determined by which of its neighbors are protected by other searchers. In this paper, we show that the minimum number of searchers required to clear the graph is the same in deduction as in constrained versions of other previously studied graph processes, namely zero forcing and fast-mixed search. We give a structural characterization, new bounds and a spectrum result on the number of searchers required. We consider the complexity of computing this parameter, giving an NP-completeness result for arbitrary graphs, and exhibiting families of graphs for which the parameter can be computed in polynomial time. We also describe properties of the deduction process related to the timing of searcher movement and the success of terminal layouts. |
| title | Deduction, Constrained Zero Forcing, and Constrained Searching |
| topic | Combinatorics Discrete Mathematics 05C57, 05C85 |
| url | https://arxiv.org/abs/2410.22962 |