✦ LIBER ✦

On Meyniel's conjecture of the cop number

✍ Scribed by Linyuan Lu; Xing Peng

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 152 KB
Volume: 71
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20642

No coin nor oath required. For personal study only.

✦ Synopsis

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 connected graphs, we prove , improving the best previously known upper‐bound O(n/ ln__n__) due to Chiniforooshan.

📜 SIMILAR VOLUMES

On the orientation of meyniel graphs

✍ Mostaffa Blidia; Pierre Duchet; Frédéric Maffray 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 360 KB

## Abstract A kernel of a directed graph is a set of vertices __K__ that is both absorbant and independent (i.e., every vertex not in __K__ is the origin of an arc whose extremity is in __K__, and no arc of the graph has both endpoints in __K__). In 1983, Meyniel conjectured that any perfect graph,

On the tamagawa number conjecture for he

On the tamagawa number conjecture for hecke characters

✍ Francesc Bars 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 268 KB

## Abstract In this paper, we prove the weak __p__‐part of the Tamagawa number conjecture in all non‐critical cases for the motives associated to Hecke characters of the form $\varphi ^a\overline{\varphi }^b$ where φ is the Hecke character of a CM elliptic curve __E__ defined over an imaginary quad

Proof of a conjecture on fractional Rams

Proof of a conjecture on fractional Ramsey numbers

✍ Jason Brown; Richard Hoshino 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 1 views

## Abstract Jacobson, Levin, and Scheinerman introduced the fractional Ramsey function __r__~__f__~ (__a__~1~, __a__~2~, …, __a__~__k__~) as an extension of the classical definition for Ramsey numbers. They determined an exact formula for the fractional Ramsey function for the case __k__=2. In this

On the Thomassen's conjecture

✍ Jianping Li 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB

## Abstract C. Thomassen proposed a conjecture: Let __G__ be a __k__‐connected graph with the stability number α ≥ __k__, then __G__ has a cycle __C__ containing __k__ independent vertices and all their neighbors. In this paper, we will obtain the following result: Let __G__ be a __k__‐connected gr

On the Erd�s-S�s conjecture

✍ Wo?niak, Mariusz 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 337 KB

Erdos and Sos conjectured in 1963 that if G is a graph of order n and size e(G) with e(G) > $ n(k -I), then G contains every tree T of size k. W e present some partial results; in particular the proof of the conjecture in the case k = n -3 0 1996 John

The Proof of a Conjecture of Additive Nu

The Proof of a Conjecture of Additive Number Theory

✍ Alexandru Gica 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 94 KB

The aim of this paper is to show that for any n ¥ N, n > 3, there exist a, b ¥ N\* such that n=a+b, the ''lengths'' of a and b having the same parity (see the text for the definition of the ''length'' of a natural number). Also we will show that for any n ¥ N, n > 2, n ] 5, 10, there exist a, b ¥ N\