✦ LIBER ✦

Weakly Pancyclic Graphs

✍ Scribed by Béla Bollobás; Andrew Thomason

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 145 KB
Volume: 77
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1999.1916

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is called weakly pancyclic if it contains cycles of all lengths between its girth and circumference. A substantial result of Ha ggkvist, Faudree, and Schelp (1981) states that a Hamiltonian non-bipartite graph of order n and size at least w(n&1) 2 Â4x+2 contains cycles of every length l, 3 l n. From this, Brandt (1997) deduced that every non-bipartite graph of the stated order and size is weakly pancyclic. He conjectured the much stronger assertion that it suffices to demand that the size be at least Wn 2 Â4X&n+5. We almost prove this conjecture by establishing that every graph of order n and size at least wn 2 Â4x&n+59 is weakly pancyclic or bipartite.

📜 SIMILAR VOLUMES

Weakly pancyclic graphs

✍ Brandt, Stephan; Faudree, Ralph; Goddard, Wayne 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 517 KB

In generalizing the concept of a pancyclic graph, we say that a graph is ''weakly pancyclic'' if it contains cycles of every length between the length of a shortest and a longest cycle. In this paper it is shown that in many cases the requirements on a graph which ensure that it is weakly pancyclic

On the girth of hamiltonian weakly pancy

On the girth of hamiltonian weakly pancyclic graphs

✍ Bollob�s, B�la; Thomason, Andrew 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 2 views

A graph is called weakly pancyclic if it contains cycles of all lengths between its girth and circumference. In answer to a question of Erdős, we show that a Hamiltonian weakly-pancyclic graph of order n can have girth as large as about 2 n/ log n. In contrast to this, we show that the existence of

Pancyclic oriented graphs

✍ Zeng Min Song 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 324 KB

## Abstract Let __D__ be an oriented graph of order __n__ ≧ 9 and minimum degree __n__ − 2. This paper proves that __D__ is pancyclic if for any two vertices __u__ and __v__, either __uv__ ≅ __A(D)__, or __d__~__D__~^+^(__u__) + __d__~__D__~^−^(__v__) ≧ __n__ − 3.

Locally Pancyclic Graphs

✍ Ladislav Stacho 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 215 KB

We prove the following theorem. Let G be a graph of order n and let W V(G). If |W | 3 and d G (x)+d G ( y) n for every pair of non-adjacent vertices x, y # W, then either G contains cycles C 3 ,

Pancyclic subgraphs of random graphs

✍ Choongbum Lee; Wojciech Samotij 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB

## Abstract An __n__‐vertex graph is called pancyclic if it contains a cycle of length __t__ for all 3≤__t__≤__n__. In this article, we study pancyclicity of random graphs in the context of resilience, and prove that if __p__>__n__^−1/2^, then the random graph __G__(__n, p__) a.a.s. satisfies the f

Pancyclicity of connected circulant grap

Pancyclicity of connected circulant graphs

✍ Bogdanowicz, Z. R. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 299 KB 👁 1 views

The circulant G,(al,. . . , ak), where 0 < al < ... < a k < ( n + 1 ) / 2 , is defined as the vertex-transitive graph that has vertices ifal,. . . ,if a k (mod n) adjacent to each vertex i. In this work we show that the connected circulants of degree at least three contain all even cycles. In additi