𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Cycles passing through k + 1 vertices in k-connected graphs

✍ Scribed by Jun Fujisawa; Tomoki Yamashita

Publisher
John Wiley and Sons
Year
2008
Tongue
English
Weight
149 KB
Volume
58
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this article, we prove the following theorem. Let k β‰₯ 3 be an integer, G be a k‐connected graph with minimum degree d and X be a set of k + 1 vertices on a cycle. Then G has a cycle of length at least min {2d,|V(G)|} passing through X. This result gives the positive answer to the Question posed by Locke [8]. Β© 2008 Wiley Periodicals, Inc. J Graph Theory 58:179–190, 2008

πŸ“œ SIMILAR VOLUMES

Circuits through prescribed vertices in
Circuits through prescribed vertices in k-connected k-regular graphs
✍ Roland HΓ€ggkvist; Wolfgang Mader πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons 🌐 English βš– 178 KB πŸ‘ 1 views

## Abstract We show that every set of $k+\lfloor{1\over 3}\sqrt{k}\rfloor$ vertices in a __k__‐connected __k__‐regular graph belongs to some circuit. Β© 2002 John Wiley & Sons, Inc. J Graph Theory 39: 145–163, 2002

Nonseparating cycles in K-Connected grap
Nonseparating cycles in K-Connected graphs
✍ Carsten Thomassen πŸ“‚ Article πŸ“… 1981 πŸ› John Wiley and Sons 🌐 English βš– 192 KB πŸ‘ 1 views

## Abstract We show that every __k__‐connected graph with no 3‐cycle contains an edge whose contraction results in a __k__‐connected graph and use this to prove that every (__k__ + 3)‐connected graph contains a cycle whose deletion results in a __k__‐connected graph. This settles a problem of L. Lo

Heavy cycles passing through some specif
Heavy cycles passing through some specified vertices in weighted graphs
✍ Jun Fujisawa; Kiyoshi Yoshimoto; Shenggui Zhang πŸ“‚ Article πŸ“… 2005 πŸ› John Wiley and Sons 🌐 English βš– 111 KB

## Abstract A weighted graph is one in which every edge __e__ is assigned a nonnegative number, called the weight of __e__. The sum of the weights of the edges incident with a vertex Ο… is called the weighted degree of Ο…. The weight of a cycle is defined as the sum of the weights of its edges. In th

Intersections of Longest Cycles in k-Con
Intersections of Longest Cycles in k-Connected Graphs
✍ Guantao Chen; Ralph J Faudree; Ronald J Gould πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 279 KB

Let G be a connected graph, where k 2. S. Smith conjectured that every two longest cycles of G have at least k vertices in common. In this note, we show that every two longest cycles meet in at least ck 3Γ‚5 vertices, where cr0.2615. ## 1998 Academic Press In this note, we provide a lower bound on

Long cycles passing through a specified
Long cycles passing through a specified edge in a 3-connected graph
✍ Enomoto, Hikoe; Hirohata, Kazuhide; Ota, Katsuhiro πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 80 KB πŸ‘ 2 views

We prove the following theorem: For a connected noncomplete graph Then through each edge of G there passes a cycle of length β‰₯ min{|V (G)|, Ο„(G) -1}.