✦ LIBER ✦

Bipartite density and the independence ratio

✍ Scribed by Stephen C. Locke

Publisher: John Wiley and Sons
Year: 1986
Tongue: English
Weight: 237 KB
Volume: 10
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190100108

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Hamiltonian properties and the bipartite

Hamiltonian properties and the bipartite independence number

✍ Oscar Ordaz; Denise Amar; André Raspaud 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 412 KB

By using the notion of compatibility of subgraphs with a perfect matching developed for digraphs in [1], we show that if, in a balanced bipartite graph G of minimum degree 6, the maximum cardinality ebip of a balanced independent subset satisfies ~bip ~< 26 --4, then G is hamiltonian-biconnected, an

On the bipartite independence number of

On the bipartite independence number of a balanced bipartite graph

✍ Odile Favaron; Pedro Mago; Oscar Ordaz 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 603 KB

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 b

Edge density and independence ratio in t

Edge density and independence ratio in triangle-free graphs with maximum degree three

✍ Jerrold Griggs; Owen Murphy 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 548 KB

A simple polynomial-time algorithm is presented which computes independent sets of guaranteed size in connected triangle-free noncubic graphs with maximum degree 3. Let nand m denote the number of vertices and edges, respectively, and let c '= m/n denote the edge density where c < 3/2. The algorithm

On the independence ratio of a graph

✍ Michael O. Albertson; Joan P. Hutchinson 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 318 KB

## Abstract This paper presents some recent results on lower bounds for independence ratios of graphs of positive genus and shows that in a limiting sense these graphs have the same independence ratios as do planar graphs. This last result is obtained by an application of Menger's Theorem to show t

On the ultimate independence ratio of a

On the ultimate independence ratio of a graph

✍ Geňa Hahn; Pavol Hell; Svatopluk Poljak 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 479 KB

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