文献

J-GLOBAL ID：201702279273423391   整理番号：17A0963091

グラフ上でプレイされる過剰に指示された警官と強盗のゲーム

The Game of Overprescribed Cops and Robbers Played on Graphs

著者 (5件)： BONATO Anthony (Ryerson univ., ON, CAN) ,  PEREZ-GIMENEZ Xavier (Univ. Nebraska-Lincoln, NE, USA) ,  PRALAT Pawel (Ryerson univ., ON, CAN) ,  PRALAT Pawel (Fields Inst. Res. in Mathematical Sci., ON, CAN) ,  REINIGER Benjamin (Illinois Inst. Technol., IL, USA)
資料名： Graphs and Combinatorics  (Graphs and Combinatorics)
巻： 33  号： 4  ページ： 801-815  発行年： 2017年 
JST資料番号： X0108A  ISSN： 0911-0119  CODEN： GRCOE5  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： このゲームは再帰性グラフ上で行われ,各頂点は少なくとも1つのループを持っている。複数の端部は許容されるが,頂点に繋がる端部の数はゲームを行うことには差異がなく,常に,隣の頂点と結合している端部があるとする。警官集合(C)と強盗集合(R)の2人のプレイヤがいる。ゲームは離散時間のステップで進行する。警官が強盗と同じ頂点に達したら逮捕で警官の勝ちである。強盗が逃げ続けられれば強盗の勝ちである。本稿では過剰な指示を受けた警官と強盗のゲームを研究した。勝つ戦略のためには,グラフの警官数は警察の最小数である。木,格子,超立方体及び平面グラフのような多様な種類のグラフについて研究した。種々の警察の数について広い範囲の逮捕時間を考慮して,種々のグラフについて検討した。

シソーラス用語： *グラフ ,  *公務員 ,  *ゲーム ,  二人ゲーム ,  警察署 ,  平面グラフ ,  多面体 ,  捕獲
準シソーラス用語： *警官 ,  超立方体

分類 (1件)： 集合論  (AB10000I)

引用文献 (22件)：

• Aigner, M., Fromme, M.: A game of cops and robbers. Discret. Appl. Math. 8, 1-11 (1984)
• Alon, N., Seymour, P., Thomas, R.: Planar separators. SIAM J. Discret. Math. 7, 184-193 (1994)
• Berarducci, A., Intriglia, B.: On the cop number of a graph. Adv. Appl. Math. 14, 389-403 (1993)
• Bollobás, B., Kun, G., Leader, I.: Cops and robbers in a random graph. J. Combin. Theory Series B 103, 226-236 (2013)
• Bonato, A., Golovach, P., Hahn, G., Kratochvíl, J.: The capture time of a graph. Discret. Math. 309, 5588-5595 (2009)

タイトルに関連する用語 (3件)： グラフ ,  警官 ,  ゲーム