✦ LIBER ✦

On the Maximum Number of Independent Cycles in a Bipartite Graph

✍ Scribed by Hong Wang

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 404 KB
Volume: 67
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1996.0037

No coin nor oath required. For personal study only.

✦ Synopsis

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 order 4 such that all of them are vertex-disjoint. Moreover, the condition on degrees is sharp. We conjecture that when n=2k, G indeed contains k vertex-disjoint quadrilaterals.

📜 SIMILAR VOLUMES

On the maximum number of cycles in a pla

On the maximum number of cycles in a planar graph

✍ R. E. L. Aldred; Carsten Thomassen 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 142 KB 👁 2 views

## Abstract Let __G__ be a graph on __p__ vertices with __q__ edges and let __r__ = __q__ − __p__ = 1. We show that __G__ has at most ${15\over 16} 2^{r}$ cycles. We also show that if __G__ is planar, then __G__ has at most 2^__r__ − 1^ = __o__(2^__r__ − 1^) cycles. The planar result is best possib

Proof of a conjecture on cycles in a bip

Proof of a conjecture on cycles in a bipartite graph

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

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

On the number of maximal bipartite subgr

On the number of maximal bipartite subgraphs of a graph

✍ Jesper Makholm Byskov; Bolette Ammitzbøll Madsen; Bjarke Skjernaa 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 72 KB 👁 2 views

We show new lower and upper bounds on the maximum number of maximal induced bipartite subgraphs of graphs with n vertices. We present an infinite family of graphs having 105 n=10 % 1:5926 n ; such subgraphs show an upper bound of O(12 n=4 ) ¼ O(1:8613 n ) and give an algorithm that finds all maximal

On the number of hamiltonian cycles in a

On the number of hamiltonian cycles in a maximal planar graph

✍ S. L. Hakimi; E. F. Schmeichel; C. Thomassen 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 243 KB 👁 2 views

## Abstract We consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph on __p__ vertices. In particular, we construct a __p__‐vertex maximal planar graph containing exactly four Hamiltonian cycles for every __p__ ≥ 12. We also pro

On the number of cycles of length 4 in a

On the number of cycles of length 4 in a maximal planar graph

✍ Ahmad Fawzi Alameddine 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 148 KB 👁 2 views

## Abstract Let __p__ and __C__~4~ (__G__) be the number of vertices and the number of 4‐cycles of a maximal planar graph __G__, respectively. Hakimi and Schmeichel characterized those graphs __G__ for which __C__~4~ (__G__) = 1/2(__p__^2^ + 3__p__ ‐ 22). This characterization is correct if __p__ ≥

On the Maximum Number of Cyclic Triples

On the Maximum Number of Cyclic Triples in Oriented Graphs

✍ Lowell W. Beineke; Frank Harary 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 146 KB