✦ LIBER ✦

On the bipartite independence number of a balanced bipartite graph

✍ Scribed by Odile Favaron; Pedro Mago; Oscar Ordaz

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 603 KB
Volume: 121
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90537-4

No coin nor oath required. For personal study only.

✦ Synopsis

Venezuela Ap. 47567, Caracas Favaron, O., P. Mago and 0. Ordaz, On the bipartite independence number of a balanced bipartite graph, Discrete Mathematics 121 (1993) 55-63.

The bipartite independence number GI aIp of a bipartite graph G is the maximum order of a balanced independent set of G. Let 6 be the minimum degree of the graph. When G itself is balanced, we establish some relations between aglp and the size or the connectivity of G. We also prove that the condition cz BIP $ S (resp. ~(a,~ < 6 -1) implies that G is hamiltonian (resp. Hamilton-biconnected), thus improving a result of Fraisse.

📜 SIMILAR VOLUMES

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

Bipartite graphs can have any number of

Bipartite graphs can have any number of independent sets

✍ V. Linek 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 476 KB

In this paper we prove that for every positive integer n there exists a bipartite graph with exactly n independent sets.

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

The size Ramsey number of a complete bip

The size Ramsey number of a complete bipartite graph

✍ P. Erdo˝s; C.C. Rousseau 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 240 KB

Erd6s. P. and C.C. Rousseau, The size Ramsey number of a complete bipartite graph, Discrete Mathematics 113 (1993) 259-262. In this note we prove that the (diagonal) size Ramsey number of K,,.,, is bounded below by $2'2".

The maximal number of induced complete b

The maximal number of induced complete bipartite graphs

✍ Béla Bollobás; Chiê Nara; Shun-ichi Tachibana 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 230 KB

The aim of this paper is to determine the maximal number of induced K(t, t) subgraphs in graphs of given order and in graphs of given size. Given a graph G and a natural number t, denote by ft(G) the number of induced subgraphs of G isomorphic to K(t, t). Our notation is that of ; in particular, K(

On 2-factors of a bipartite graph

✍ Wang, Hong 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 191 KB 👁 2 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