Tandem-win graphs

被引：16

作者：

Clarke, NE ^{[1
]}

Nowakowski, RJ

机构：

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

[2] Dalhousie Univ, Dept Math & Stat, Halifax, NS, Canada

来源：

DISCRETE MATHEMATICS | 2005年 / 299卷 / 1-3期

关键词：

game; cop; tandem-win; pursuit; graph;

D O I：

10.1016/j.disc.2004.11.016

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this version of the Cops and Robber game, the cops move in tandems, or pairs, such that they are at distance at most one after every move. We present a recognition theorem for tandem-win graphs, and a characterization of triangle-free tandem-win graphs. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：56 / 64

页数：9

共 10 条

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

AIGNER, M ;

FROMME, M .

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

[2] ON BRIDGED GRAPHS AND COP-WIN GRAPHS [J].

ANSTEE, RP ;

FARBER, M .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1988, 44 (01) :22-28

[3]

Brandstadt A., 1999, SIAM MONOGRAPHS DISC

[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.E., 2002, THESIS DALHOUSIE U

[7]

Clarke NE, 2000, ARS COMBINATORIA, V56, P97

[8]

HAHN G, IN PRESS DISCRETE MA

[9]

Nowakowski R., 1983, DISCRETE MATH, V43, P23

[10]

Quilliot A., 1983, THESIS U PARIS 6

← 1 →