𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Tutte cycles in circuit graphs

✍ Scribed by Zhicheng Gao; Xingxing Yu

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
736 KB
Volume
182
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Jackson and Wormald showed that every 3-cormected planar graph G contains a Tutte cycle C such that each component of G-C contains less than I V(G)I/2 vertices. We prove in this paper that IV(G)[~2 can be replaced by I V(G)I/3. This answers a question of Jackson and Wormald. This result may be used to give a better lower bound on the length of a longest cycle in a 3-connected planar graph.

πŸ“œ SIMILAR VOLUMES

Tutte sets in graphs I: Maximal tutte se
Tutte sets in graphs I: Maximal tutte sets and D-graphs
✍ D. Bauer; H. J. Broersma; A. Morgana; E. Schmeichel πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 177 KB

## Abstract A well‐known formula of Tutte and Berge expresses the size of a maximum matching in a graph __G__ in terms of what is usually called the deficiency of __G__. A subset __X__ of __V__(__G__) for which this deficiency is attained is called a Tutte set of __G__. While much is known about ma

Cycles in butterfly graphs
Cycles in butterfly graphs
✍ Hwang, Shien-Ching; Chen, Gen-Huey πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 214 KB πŸ‘ 3 views

Three problems in connection with cycles on the butterfly graphs are studied in this paper. The first problem is to construct complete uniform cycle partitions for the butterfly graphs. Suppose that

Packing Cycles in Graphs
Packing Cycles in Graphs
✍ Guoli Ding; Wenan Zang πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 267 KB