Premium
Large classes of infinite k ‐cop‐win graphs
Author(s) -
Bonato Anthony,
Hahn Geňa,
Tardif Claude
Publication year - 2010
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20484
Subject(s) - mathematics , combinatorics , automorphism , vertex (graph theory) , discrete mathematics , characterization (materials science) , endomorphism , graph , transitive relation , cograph , 1 planar graph , chordal graph , materials science , nanotechnology
While finite cop‐win finite graphs possess a good structural characterization, none is known for infinite cop‐win graphs. As evidence that such a characterization might not exist, we provide as large as possible classes of infinite graphs with finite cop number. More precisely, for each infinite cardinal κ and each positive integer k , we construct 2 κ non‐isomorphic k ‐cop‐win graphs satisfying additional properties such as vertex‐transitivity, or having universal endomorphism monoid and automorphism group. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 334–342, 2010