✦ LIBER ✦

Edge disjoint cycles through specified vertices

✍ Scribed by Luis Goddyn; Ladislav Stacho

Publisher: John Wiley and Sons
Year: 2005
Tongue: English
Weight: 158 KB
Volume: 50
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20104

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We give a sufficient condition for a simple graph G to have k pairwise edge‐disjoint cycles, each of which contains a prescribed set W of vertices. The condition is that the induced subgraph G[W] be 2__k__‐connected, and that for any two vertices at distance two in G[W], at least one of the two has degree at least |V(G)|/2 + 2(k − 1) in G. This is a common generalization of special cases previously obtained by Bollobás/Brightwell (where k = 1) and Li (where W = V(G)). A key lemma is of independent interest. Let G be the complement of a bipartite graph with partite sets X, Y. If G is 2__k__ connected, then G contains k Hamilton cycles that are pairwise edge‐disjoint except for edges in G[Y]. © 2005 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

Vertex-disjoint cycles containing specif

Vertex-disjoint cycles containing specified vertices in a bipartite graph

✍ Guantao Chen; Hikoe Enomoto; Ken-ichi Kawarabayashi; Katsuhiro Ota; Dingjun Lou; 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB

## Abstract A minimum degree condition is given for a bipartite graph to contain a 2‐factor each component of which contains a previously specified vertex. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 145–166, 2004

Vertex-disjoint cycles containing prescr

Vertex-disjoint cycles containing prescribed vertices

✍ Yoshiyasu Ishigami; Tao Jiang 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 206 KB

## Abstract Enomoto 7 conjectured that if the minimum degree of a graph __G__ of order __n__ ≥ 4__k__ − 1 is at least the integer $ \left \lfloor \sqrt{n+\left (\,{9 \over 4}k^2 - 4k + 1\right)} \,+ {3 \over 2}k - 1 \right \rfloor$, then for any __k__ vertices, __G__ contains __k__ vertex‐disjoint

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

Edge disjoint cycles in graphs

✍ Li Hao 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 419 KB

Spanning Cycles Through Specified Edges

Spanning Cycles Through Specified Edges in Bipartite Graphs

✍ Reza Zamani; Douglas B. West 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 284 KB

P ósa proved that if G is an n-vertex graph in which any two nonadjacent vertices have degree-sum at least n+k, then G has a spanning cycle containing any specified family of disjoint paths with a total of k edges. We consider the analogous problem for a bipartite graph G with n vertices and parts o

Edge disjoint Hamilton cycles in graphs

✍ Guojun Li 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 2 views