✦ LIBER ✦

Biclosure and bistability in a balanced bipartite graph

✍ Scribed by Denise Amar; Odile Favaron; Pedro Mago; Oscar Ordaz

Publisher: John Wiley and Sons
Year: 1995
Tongue: English
Weight: 719 KB
Volume: 20
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190200414

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The k‐biclosure of a balanced bipartite graph wiht color classes A and B is the graph obtained from G by recursively joining pairs of nonadjacent vertices respectively taken in A and B whose degree sum is at least k, until no such pair remains. A property P defined on all the balanced bipartite graphs of order 2__n__ is k‐bistable if whenever G + ab has property P and d~G~(b) ≧ k then G itself has property P.

📜 SIMILAR VOLUMES

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

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

Neighborhood conditions for balanced ind

Neighborhood conditions for balanced independent sets in bipartite graphs

✍ Denise Amar; Stephan Brandt; Daniel Brito; Oscar Ordaz 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 319 KB

Let G be a balanced bipartite graph of order 2n and minimum degree 6(G)>~3. If, for every balanced independent set S of four vertices, IN(S)I >n then G is traceable, the circumference is at least 2n -2 and G contains a 2-factor (with only small order exceptional graphs for the latter statement). If

Maximum matching in a convex bipartite g

Maximum matching in a convex bipartite graph

✍ Fred Glover 📂 Article 📅 1967 🏛 John Wiley and Sons 🌐 English ⚖ 197 KB

Packing two bipartite graphs into a comp

Packing two bipartite graphs into a complete bipartite graph

✍ Wang, Hong 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB 👁 3 views

For two integers a and b, we say that a bipartite graph G admits an (a, b)bipartition if G has a bipartition (X, Y ) such that |X| = a and |Y | = b. We say that two bipartite graphs G and H are compatible if, for some integers a and b, both G and H admit (a, b)-bipartitions. In this paper, we prove

Bipartite cubic graphs and a shortness e

Bipartite cubic graphs and a shortness exponent

✍ P.J. Owens 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 148 KB

The class of 3-connected bipartite cubic graphs is shown to contain a oon-Hamiltonian graph with only 78 vertices and to have a shortness exponent less than one. In this paper, a graph is a simple undirected gaph and a subgraph is an induced subgraph. For a~ay graph G, v(G) denotes the number of ve