DECOMPOSITION OF WHEEL-AND-PARACHUTE-FREE BALANCED BIPARTITE GRAPHS

A wheel in a bipartite graph is an induced subgraph defined by a chord less cycle H together with a node upsilon having at least three neighb ors in H. A parachute in a bipartite graph is an induced subgraph defi ned by four chordless paths T, P-1, P-2, M of positive lengths, T = up silon(1), ..., upsilon(2); P-1 = upsilon(1), ..., z; P-2 = upsilon(2) ..., z; M = upsilon, ..., z, where (upsilon(1), upsilon(2), upsilon, z ) are distinct nodes, and two edges upsilon upsilon(1) and upsilon ups ilon(2). The parachute contains no other edge except the ones mentione d above. Furthermore \E(P-1)\+\E(P-2)\greater than or equal to 3. A cy cle C in a bipartite graph is said to be quad if its length is congrue nt to 0 mod 4. C is unquad if its length is congruent to 2 mod 4. In t his paper we consider bipartite graphs that do not contain a wheel, a parachute and an unquad chordless cycle as induced subgraphs. These gr aphs are called WP-free balanced bipartite graphs and we prove the fol lowing theorem: At least one of the following alternatives holds for a WP-free balanced bipartite graph G: G contains no unquad cycle with a unique chord. G contains an unquad cycle C having unique chord u upsi lon, and four disjoint node sets B, D, E, F such that the node sets B boolean OR D, E boolean OR F and B boolean OR E induce complete bipart ite graphs K-BD, K-EF and K-BE with the following properties: -The rem oval of the edges of both K-BD and K-EF disconnects G. - Node u belong s to B and upsilon belongs to E. Furthermore the removal of the nodes in K-BE disconnects G. To a 0, 1 matrix A we associate a bipartite gra ph G(V-r, V-c; E) as follows: The node sets V-r and V-c represent the row set and the column set of A and edge ij belongs to E if and only i f a(ij) = 1. A 0, 1 matrix A is balanced if A does not contain a squar e submatrix of odd order with two ones per row and per column. Balance d matrices are important in integer programming and combinatorial opti mization since the associated set packing and set covering polytopes h ave integral vertices. A 0, 1 matrix is balanced if and only if the as sociated bipartite graph does not contain an unquad chordless cycle. I n this case, we say that the bipartite graph is balanced. Hence WP-fre e balanced bipartite graphs are a subclass of balanced bipartite graph s. The following subclasses of balanced bipartite graphs are WP-free a nd have been extensively studied. Totally balanced bipartite graphs ar e the ones not containing a chordless cycle of length greater than fou r. Strongly balanced bipartite graphs are the ones not containing an u nquad cycle with less than two chords. The above theorem generalizes d ecomposition theorems for these classes of graphs and yields a polynom ial algorithm to test whether a bipartite graph is WP-free and balance d.