✦ LIBER ✦

Proof of a conjecture on cycles in a bipartite graph

✍ Scribed by Wang, Hong

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 244 KB
Volume: 31
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199908)31:4<333::aid-jgt8>3.0.co;2-4

No coin nor oath required. For personal study only.

✦ Synopsis

It was conjectured in [Wang, to appear in The Australasian Journal of Combinatorics] that, for each integer k ≥ 2, there exists

. This conjecture is also verified for k = 2, 3 in [Wang, to appear; Wang, manuscript]. In this article, we prove this conjecture to be true if n ≥ 3k, i.e., M (k) ≤ 3k. We will also show that, if n ≥ 3k, then for any k independent edges e 1 , . . . , e k of G, there exist k vertex-disjoint cycles C 1 , . . . , C k of length at most 6 in G such that e i ∈ E(C i ) for all i ∈ {1, . . . , k}.

📜 SIMILAR VOLUMES

On 2-factors of a bipartite graph

✍ Wang, Hong 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 191 KB 👁 1 views

In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2-factor with exactly k components? We will prove that if , then, for any bipartite graph H = (U 1 , U 2 ; F ) with |U 1 | ≤ n, |U 2 | ≤ n and ∆(H) ≤ 2, G contains a subgraph i

On a conjecture of Aris: Proof and remar

On a conjecture of Aris: Proof and remarks

✍ Dan Luss; Neal R. Amundson 📂 Article 📅 1967 🏛 American Institute of Chemical Engineers 🌐 English ⚖ 428 KB 👁 1 views

A short proof of a theorem on Hamiltonia

A short proof of a theorem on Hamiltonian graphs

✍ Ainouche, A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB 👁 2 views

In this note, w e give a short proof of a stronger version of the following theorem: Let G be a 2-connected graph of order n such that for any independent set {u, u , w}, then G is hamiltonian. 0 1996 John

On the cycle polytope of a directed grap

On the cycle polytope of a directed graph

✍ Egon Balas; Maarten Oosten 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 185 KB

An addendum to the most vital edges of m

An addendum to the most vital edges of matching in a bipartite graph

✍ Volgenant, A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 50 KB 👁 2 views

Cycles in a graph whose lengths differ b

Cycles in a graph whose lengths differ by one or two

✍ Bondy, J. A.; Vince, A. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 116 KB 👁 2 views

Several problems concerning the distribution of cycle lengths in a graph have been proposed by P. Erdös and colleagues. In this note two variations of the following such question are answered. In a simple graph where every vertex has degree at least three, must there exist two cycles whose lengths d