𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Large classes of infinite k-cop-win graphs

✍ Scribed by Anthony Bonato; Geňa Hahn; Claude Tardif

Publisher
John Wiley and Sons
Year
2010
Tongue
English
Weight
104 KB
Volume
65
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 Contract grant sponsors: NSERC; MITACS.

📜 SIMILAR VOLUMES

Mutation classes of diagrams via infinit
Mutation classes of diagrams via infinite graphs
✍ Thilo Henrich 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 260 KB 👁 1 views

## Abstract We give a complete description of the cluster‐mutation classes of diagrams of Dynkin types \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathbb {A},\mathbb {B},\mathbb {D}$\end{document} and of affine Dynkin types \documentclass{article}\usepackage{amssym

An infinite class of reach-preservable g
An infinite class of reach-preservable graphs
✍ Gagliardi, Daniel; Lewinter, Marty 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 42 KB 👁 1 views

for all w in G. G is called reach-preservable if each of its spanning trees contains at least one reachpreserving vertex. We show that K 2,n is reach-preservable. We show that a graph is bipartite if and only if given any pair of vertices, there exists a spanning tree in which both vertices a reach-

k-Bounded classes of dominant-independen
k-Bounded classes of dominant-independent perfect graphs
✍ Zverovich, Igor E. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 253 KB 👁 2 views

Let α(G), γ(G), and i(G) be the independence number, the domination number, and the independent domination number of a graph G, respectively. For any k ≥ 0, we define the following hereditary classes: αi where ISub(G) is the set of all induced subgraphs of a graph G. In this article, we present a f

Subdivisions of large complete bipartite
Subdivisions of large complete bipartite graphs and long induced paths in k-connected graphs
✍ Thomas Böhme; Bojan Mohar; Riste Škrekovski; Michael Stiebitz 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 67 KB 👁 1 views

## Abstract It is proved that for every positive integers __k__, __r__ and __s__ there exists an integer __n__ = __n__(__k__,__r__,__s__) such that every __k__‐connected graph of order at least __n__ contains either an induced path of length __s__ or a subdivision of the complete bipartite graph __

The existence of a 2-factor in K1, n-fre
The existence of a 2-factor in K1, n-free graphs with large connectivity and large edge-connectivity
✍ R. E. L. Aldred; Yoshimi Egawa; Jun Fujisawa; Katsuhiro Ota; Akira Saito 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 1 views

In this article, we study the existence of a 2-factor in a K 1,nfree graph. Sumner [J London Math Soc 13 (1976), 351-359] proved that for n ≥ 4, an (n-1)-connected K 1,n -free graph of even order has a 1-factor.