✦ LIBER ✦

Locally Pancyclic Graphs

✍ Scribed by Ladislav Stacho

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 215 KB
Volume: 76
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1998.1885

No coin nor oath required. For personal study only.

✦ Synopsis

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 ,

📜 SIMILAR VOLUMES

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.

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

Weakly Pancyclic Graphs

✍ Béla Bollobás; Andrew Thomason 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 145 KB

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

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

Locally semicomplete digraphs that are c

Locally semicomplete digraphs that are complementarym-pancyclic

✍ Guo, Yubao; Volkmann, Lutz 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 923 KB

If A and Bare two subdigraphs of D, then we denote by &(A, 5) the distance between A and 5. Let D be a 2-connected locally semicomplete digraph on n 2 6 vertices. If S is a minimum separating set of D and d = min{do-s(N+(s) -S, N-(s) -S ) l s E S}, then rn = max(3, d + 2) I n/2 and D contains t w o