Characterizations of k-copwin graphs

被引：32

作者：

Clarke, Nancy E. ^{[2
]}

MacGillivray, Gary ^{[1
]}

机构：

[1] Univ Victoria, Dept Math & Stat, Victoria, BC, Canada

[2] Acadia Univ, Dept Math & Stat, Wolfville, NS B0P 1X0, Canada

来源：

DISCRETE MATHEMATICS | 2012年 / 312卷 / 08期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Pursuit game; Cops and robber; WIN GRAPHS; ROBBER; COPS;

D O I：

10.1016/j.disc.2012.01.002

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We give two characterizations of the graphs on which k cops have a winning strategy in the game of Cops and Robber. One of these is in terms of an order relation, and one is in terms of a vertex ordering. Both generalize characterizations known for the case k = 1. (C) 2012 Elsevier B.V. All rights reserved.

引用

页码：1421 / 1425

页数：5

共 14 条

[1] A GAME OF COPS AND ROBBERS [J].

AIGNER, M ;

FROMME, M .

DISCRETE APPLIED MATHEMATICS, 1984, 8 (01) :1-12

[2] ON THE COP NUMBER OF A GRAPH [J].

BERARDUCCI, A ;

INTRIGILA, B .

ADVANCES IN APPLIED MATHEMATICS, 1993, 14 (04) :389-403

[3] Cops and Robbers from a distance [J].

Bonato, Anthony ;

Chiniforooshan, Ehsan ;

Pralat, Pawel .

THEORETICAL COMPUTER SCIENCE, 2010, 411 (43) :3834-3844

[4] Bridged graphs are cop-win graphs: An algorithmic proof [J].

Chepoi, V .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1997, 69 (01) :97-100

[5] On distance-preserving and domination elimination orderings [J].

Chepoi, V .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1998, 11 (03) :414-436

[6]

Clarke N., 1999, THESIS DALHOUSIE U

[7]

Clarke N. E., 2005, Discussiones Mathematicae Graph Theory, V25, P241, DOI 10.7151/dmgt.1277

[8]

Clarke N.E., 2002, THESIS DALHOUSIE U

[9]

Clarke NE, 2000, ARS COMBINATORIA, V56, P97

[10] Tandem-win graphs [J].

Clarke, NE ;

Nowakowski, RJ .

DISCRETE MATHEMATICS, 2005, 299 (1-3) :56-64

← 1 2 →