Secure domination in P 5 P_{5} -free graphs
2025
Read Secure domination in P 5 P_{5} -free graphs (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-08088.txt.
Description
Uttam Gupta, Michael Henning, Paras Maniya, and Dinabandhu Pradhan prove bounds on a safety-minded form of guard placement in networks, in a 2025 mathematics paper. A network is modelled as a graph of points and links. A guard set watches every point. A secure guard set adds a swap rule: any unwatched point can trade places with a neighbouring guard and leave the network still watched. The smallest such set is the secure domination number.
The results apply to graphs that avoid a path on five points as a pattern. For those graphs, the secure number is at most one and a half times the size of the largest set of points with no links among them. For narrower families that also avoid certain small patterns, the bound drops further, in some cases to that count plus one. The proofs sharpen what is known about cheap, safe coverage.
Catalog record
| YEAR | 2025 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 19 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-08088