On a contraction-like property of dismantlable graphs

被引：1

作者：

Luckraz, Shravan ^{[1
]}

机构：

[1] Zhejiang Univ Finance & Econ, Sch Publ Finance & Taxat, Hangzhou 310018, Peoples R China

来源：

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS | 2023年 / 423卷

关键词：

Graph theory; Game theory; Pursuit games; GAME; COPS; ROBBERS;

D O I：

10.1016/j.cam.2022.114992

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In a recent paper, Baradol, Gopal and Radenovic (2020) study the contraction properties of mappings on rectangular metric spaces endowed with a digraph. In this paper, we show that a class of mappings on dismantlable undirected graphs have a natural contraction-like property acting on a spanning tree of the graph. We propose further characterizations of dismantlable graphs and apply our results to pursuit-evasion games on graphs. (c) 2022 Elsevier B.V. All rights reserved.

引用

页数：9

共 11 条

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

AIGNER, M ;

FROMME, M .

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

[2] Computational fixed points in graphical rectangular metric spaces with application [J].

Baradol, Pravin ;

Gopal, Dhananjay ;

Radenovic, Stojan .

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2020, 375

[3]

Bonato A., 2011, The Game of Cops and Robbers on Graphs

[4] Gibbs measures and dismantlable graphs [J].

Brightwell, GR ;

Winkler, P .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2000, 78 (01) :141-166

[5] A note on k-cop, l-robber games on graphs [J].

Hahn, Gena ;

MacGillivray, Gary .

DISCRETE MATHEMATICS, 2006, 306 (19-20) :2492-2497

[6] On a Characterization of Evasion Strategies for Pursuit-Evasion Games on Graphs [J].

Ibragimov, Gafurjan ;

Luckraz, Shravan .

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2017, 175 (02) :590-596

[7] A Note on Some Weaker Notions of Cop-Win and Robber-Win Graphs [J].

Luckraz, Shravan ;

Ibragimov, Gafurjan ;

Pansera, Bruno Antonio .

MATHEMATICS, 2022, 10 (22)

[8] A Survey on the Relationship Between the Game of Cops and Robbers and Other Game Representations [J].

Luckraz, Shravan .

DYNAMIC GAMES AND APPLICATIONS, 2019, 9 (02) :506-520

[9] A game of cops and robbers played on products of graphs [J].

Neufeld, S ;

Nowakowski, R .

DISCRETE MATHEMATICS, 1998, 186 (1-3) :253-268

[10] VERTEX-TO-VERTEX PURSUIT IN A GRAPH [J].

NOWAKOWSKI, R ;

WINKLER, P .

DISCRETE MATHEMATICS, 1983, 43 (2-3) :235-239

← 1 2 →