✦ LIBER ✦

Spanning Cycles Through Specified Edges in Bipartite Graphs

✍ Scribed by Reza Zamani; Douglas B. West

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 284 KB
Volume: 71
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20627

No coin nor oath required. For personal study only.

✦ Synopsis

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 of equal size. Let F be a subgraph of G whose components are nontrivial paths. Let k be the number of edges in F , and let t 1 and t 2 be the numbers of components of F having odd and even length, respectively. We prove that G has a spanning cycle containing F if any two nonadjacent vertices in opposite partite sets have degree-sum at least n / 2+ (F ), where (F ) = k /2 + (here = 1 if t 1 = 0 or if (t 1 , t 2 ) ∈{(1, 0), (2, 0)}, and = 0 otherwise). We show also that this threshold on the degree-sum is sharp when n > 3k.

📜 SIMILAR VOLUMES

Edge disjoint cycles through specified v

Edge disjoint cycles through specified vertices

✍ Luis Goddyn; Ladislav Stacho 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 158 KB

## 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 _

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}.

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

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

Long cycles passing through a specified

Long cycles passing through a specified path in a graph

✍ Hirohata, Kazuhide 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 247 KB 👁 2 views

## For a graph G and an integer an independent set of vertices in G}. Enomoto proved the following theorem. Let s ≥ 1 and let G be a (s + 2)-connected graph. Then G has a cycle of length ≥ min{|V (G)|, σ 2 (G) -s} passing through any path of length s. We generalize this result as follows. Let k ≥

Longest paths and cycles in bipartite or

Longest paths and cycles in bipartite oriented graphs

✍ Zhang Ke Min 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 430 KB 👁 1 views

In this paper we obtain two sufficient conditions, Ore type (Theorem 1) and Dirac type (Theorem 2). on the degrees of a bipartite oriented graph for ensuring the existence of long paths and cycles. These conditions are shown to be the best possible in a sense. An oriented graph is a digraph without