𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The longest cycle of a graph with a large minimal degree

✍ Scribed by Noga Alon

Publisher
John Wiley and Sons
Year
1986
Tongue
English
Weight
214 KB
Volume
10
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

We show that every graph G on n vertices with minimal degree at least n / k contains a cycle of length at least [ n / ( k -111. This verifies a conjecture of Katchalski. When k = 2 our result reduces t o the classical theorem of Dirac that asserts that if all degrees are at least i n then G is Hamiltonian.

πŸ“œ SIMILAR VOLUMES

Cycles and paths in graphs with large mi
Cycles and paths in graphs with large minimal degree
✍ V. Nikiforov; R. H. Schelp πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 114 KB πŸ‘ 1 views

## Abstract Let __G__ be a simple graph of order __n__ and minimal degree > cn (0 < c < 1/2). We prove that (1) There exist __n__~0~ = __n__~0~(__c__) and __k__ = __k__(__c__) such that if __n__ > __n__~0~ and __G__ contains a cycle __C__~__t__~ for some __t__ > 2__k__, then __G__ contains a cycle

A degree sum condition for longest cycle
A degree sum condition for longest cycles in 3-connected graphs
✍ Tomoki Yamashita πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 110 KB πŸ‘ 1 views

## Abstract For a graph __G__, we denote by __d__~__G__~(__x__) and ΞΊ(__G__) the degree of a vertex __x__ in __G__ and the connectivity of __G__, respectively. In this article, we show that if __G__ is a 3‐connected graph of order __n__ such that __d__~__G__~(__x__) + __d__~__G__~(__y__) + __d__~__

Revised Greedy algorithm for formation o
Revised Greedy algorithm for formation of a minimal cycle basis of a graph
✍ Kaveh, A. ;Roosta, G. R. πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 356 KB πŸ‘ 1 views

## SUM MARY An efficient algorithm is developed for the formation of a minimal cycle basis of a graph. This method reduces the number of cycles to be considered as (candidates for being the elements of a minimal basis and makes practical use of the Greedy algorithm feasible. A comparison is made b

A sharp lower bound for the circumferenc
A sharp lower bound for the circumference of 1-tough graphs with large degree sums
✍ Vu Dinh Hoa πŸ“‚ Article πŸ“… 1995 πŸ› John Wiley and Sons 🌐 English βš– 207 KB πŸ‘ 1 views

## Abstract We show that every 1‐tough graph __G__ on __n__ β‰₯ 3 vertices with Οƒ~3~≧ __n__ has a cycle of length at least min{__n, n__ + (Οƒ~3~/3 ) βˆ’ Ξ± + 1}, where Οƒ~3~ denotes the minimum value of the degree sum of any 3 pairwise nonadjacent vertices and Ξ± the cardinality of a miximum independent se