𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Cycles in bipartite graphs and an application in number theory

✍ Scribed by Gábor N. Sárközy

Publisher
John Wiley and Sons
Year
1995
Tongue
English
Weight
304 KB
Volume
19
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Let G = G(A, B) be a bipartite graph with IAl = u, IBl = U , and let I be a positive integer. In this paper we prove the following result: If u 4 u, uu 5 n, rn = J€(G)I, and

then G contains a C2/.

📜 SIMILAR VOLUMES

Balanced cycles and holes in bipartite g
Balanced cycles and holes in bipartite graphs
✍ Michele Conforti; Gérard Cornuéjols; Kristina Vušković 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 414 KB

Bruce Reed asks the following question: Can we determine whether a bipartite graph contains a chordless cycle whose length is a multiple of 4? We show that the two following more general questions are equivalent and we provide an answer. Given a bipartite graph G where each edge is assigned a weight

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

On the Maximum Number of Independent Cyc
On the Maximum Number of Independent Cycles in a Bipartite Graph
✍ Hong Wang 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 404 KB

Let G=(V 1 , V 2 ; E ) be a bipartite graph with |V 1 |= |V 2 | =n 2k, where k is a positive integer. Suppose that the minimum degree of G is at least k+1. We show that if n>2k, then G contains k vertex-disjoint cycles. We also show that if n=2k, then G contains k&1 quadrilaterals and a path of orde

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

Alternating hamiltonian cycles in two co
Alternating hamiltonian cycles in two colored complete bipartite graphs
✍ A. G. Chetwynd; A. J. W. Hilton 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 269 KB 👁 2 views

## Abstract We give necessary and sufficient conditions for the existence of an alternating Hamiltonian cycle in a complete bipartite graph whose edge set is colored with two colors.