(叉，偶洞)-Free图上的警察抓小偷问题
Cops and Robbers on (Fork, Even-Hole)-Free Graphs
摘要: 叉(fork)是由一个爪图K
1,3与其一条边相连的额外顶点构成的图;偶洞(even-hole)是长度为偶数且至少为4 的诱导环。(叉，偶洞)-free图是不包含叉或偶洞作为诱导子图的图。本文主要研究了警察抓小偷游戏在(叉，偶洞)-free图上的情形。首先，通过广度优先搜索层分解研究了这类图的结构性质，随后在满足这类图的性质条件下，讨论了3名警察抓住小偷的策略并证明警察数至多为3，进而推广了Javadi 和Momeni关于(爪，偶洞)-free图的研究结果。
Abstract: A fork is a graph obtained from a claw K1,3 by attaching an additional vertex to one of its edges, and an even-hole is an induced cycle of even length at least four. A (fork; even-hole)-free graph is one that contains neither a fork nor an even-hole as an induced subgraph. In this paper, we study the game of cops and robbers on this class of graphs. We first analyze the structural properties of these graphs via a breadth-first search (BFS) layering decomposition. Based on these properties, we then develop a strategy whereby three cops can capture the robber and prove that their cop number is at most 3, thereby extending the results of Javadi and Momeni on (claw; even-hole)-free graphs.
参考文献
|
[1]
|
Aigner, M. and Fromme, M. (1984) A Game of Cops and Robbers. Discrete Applied Mathe-
matics, 8, 1-12. [Google Scholar] [CrossRef]
|
|
[2]
|
Nowakowski, R. and Winkler, P. (1983) Vertex-to-Vertex Pursuit in a Graph. Discrete Math-
ematics, 43, 235-239. [Google Scholar] [CrossRef]
|
|
[3]
|
Quilliot, A. (1978) These de 3e Cycle. PhD Thesis, Univ. Paris VI.
|
|
[4]
|
Joret, G., Kaminski, M. and Theis, D.O. (2010) The Cops and Robber Game on Graphs with
Forbidden (Induced) Subgraphs. Contributions to Discrete Mathematics, 5, 40-51. [Google Scholar] [CrossRef]
|
|
[5]
|
Sivaraman, V. (2019) Cop Number of Graphs without Long Holes. arXiv:2001.00477
|
|
[6]
|
Chudnovsky, M., Norin, S., Seymour, P.D. and Turcotte, J. (2024) Cops and Robbers on P5-
Free Graphs. SIAM Journal on Discrete Mathematics, 38, 845-856.[CrossRef]
|
|
[7]
|
Cameron, K., da Silva, M.V.G., Huang, S. and Vuskovic, K. (2018) Structure and Algorithms
for (Cap, Even Hole)-Free Graphs. Discrete Mathematics, 341, 463-473. [Google Scholar] [CrossRef]
|
|
[8]
|
Scott, A. and Seymour, P. (2016) Induced Subgraphs of Graphs with Large Chromatic Number.
I. Odd Holes. Journal of Combinatorial Theory, Series B, 121, 68-84. [Google Scholar] [CrossRef]
|
|
[9]
|
Javadi, R., Momeni, A. (2022) The Game of Cops and Robber on (Claw, Even-Hole)-Free
Graphs. arXiv:2112.07503
|
|
[10]
|
Wolk, E.S. (1965) A Note on \The Comparability Graph of a Tree". Proceedings of the Amer-
ican Mathematical Society, 16, 17-20. [Google Scholar] [CrossRef]
|