✦ LIBER ✦

On the Cop Number of a Graph

✍ Scribed by A. Berarducci; B. Intrigila

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 608 KB
Volume: 14
Category: Article
ISSN: 0196-8858
DOI: 10.1006/aama.1993.1019

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A better bound for the cop number of gen

A better bound for the cop number of general graphs

✍ Ehsan Chiniforooshan 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 85 KB

## Abstract In this note, we prove that the cop number of any __n__‐vertex graph __G__, denoted by ${{c}}({{G}})$, is at most ${{O}}\big({{{n}}\over {{\rm lg}} {{n}}}\big)$. Meyniel conjectured ${{c}}({{G}})={{O}}(\sqrt{{{n}}})$. It appears that the best previously known sublinear upper‐bound is du

On Meyniel's conjecture of the cop numbe

On Meyniel's conjecture of the cop number

✍ Linyuan Lu; Xing Peng 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB

## Abstract Meyniel conjectured that the cop number __c__(__G__) of any connected graph __G__ on __n__ vertices is at most for some constant __C__. In this article, we prove Meyniel's conjecture in special cases that __G__ has diameter 2 or __G__ is a bipartite graph of diameter 3. For general con

On the geodetic number of a graph

✍ Gary Chartrand; Frank Harary; Ping Zhang 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 308 KB

On the separation number of a graph

✍ Zevi Miller; Dan Pritikin 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 781 KB

We consider the following graph labeling problem, introduced by Leung et al. (3. Y-T. Leung, 0. Vornberger, and J. D. Witthoff, On some variants of the bandwidth minimization problem. SIAM J. Comput. 13 (1984) 650-667). Let G be a graph of order n, and f a bijection from the separation number of G,

On the bondage number of a graph

✍ Yue-Li Wang 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 162 KB

The bondage number b(G) of a graph G is the minimum cardinality of a set of edges of G whose removal from G makes the domination number of G increase. There are several papers discussed the upper bound of b(G). In this paper, we shall give an improved upper bound of b(G).

On the Interval Number of a Triangulated

On the Interval Number of a Triangulated Graph

✍ Thomas Andreae 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 414 KB 👁 2 views

The interval number of a simple undirected graph G, denoted i(G), is the least nonnegative integer r for which we can assign to each vertex in G a collection of at most r intervals on the real line such that two distinct vertices u and w of G are adjacent if and only if some interval for u intersect