Please use this identifier to cite or link to this item: https://repository.iimb.ac.in/handle/2074/10374
DC FieldValueLanguage
dc.contributor.authorConforti, Michele-
dc.contributor.authorCornuéjols, Gérard-
dc.contributor.authorRao, Mendu Rammohan-
dc.date.accessioned2019-11-05T14:21:16Z-
dc.date.available2019-11-05T14:21:16Z-
dc.date.issued1995-
dc.identifier.urihttp://repository.iimb.ac.in/handle/2074/10374-
dc.description.abstractA wheel in a bipartite graph is an induced subgraph defined by a chordless cycle H together with a node v having at least three neighbors in H. A parachute in a bipartite graph is an induced subgraph defined by four chordless paths T,P1,P2,M of positive lengths, T = v1, …, v2; P1 = v1,…, z; P2 = v2, …, z; M = v,…, z, where (v1,v2,v,z) are distinct nodes, and two edges vv1 and vv2. The parachute contains no other edge except the ones mentioned above. Furthermore ¦E(P1)¦ + ¦E(P2)¦ ⩾ 3. A cycle C in a bipartite graph is said to be quad if its length is congruent to 0 mod 4. C is unquad if its length is congruent to 2 mod 4. In this paper we consider bipartite graphs that do not contain a wheel, a parachute and an unquad chordless cycle as induced subgraphs. These graphs are called WP-free balanced bipartite graphs and we prove the following 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 uv, and four disjoint node sets B, D, E, F such that the node sets B∪D, E∪F and B∪E induce complete bipartite graphs KBD, KEF and KBE with the following properties: ◦ The removal of the edges of both KBD and KEF disconnects G. ◦ Node u belongs to B and v belongs to E. Furthermore the removal of the nodes in KBE disconnects G. To a 0, 1 matrix A we associate a bipartite graph G(Vr, Vc; E) as follows: The node sets Vr and Vc represent the row set and the column set of A and edge ij belongs to E if and only if aij = 1. A 0, 1 matrix A is balanced if A does not contain a square submatrix of odd order with two ones per row and per column. Balanced matrices are important in integer programming and combinatorial optimization since the associated set packing and set covering polytopes have integral vertices. A 0, 1 matrix is balanced if and only if the associated bipartite graph does not contain an unquad chordless cycle. In this case, we say that the bipartite graph is balanced. Hence WP-free balanced bipartite graphs are a subclass of balanced bipartite graphs. The following subclasses of balanced bipartite graphs are WP-free and have been extensively studied. Totally balanced bipartite graphs are the ones not containing a chordless cycle of length greater than four. Strongly balanced bipartite graphs are the ones not containing an unquad cycle with less than two chords. The above theorem generalizes decomposition theorems for these classes of graphs and yields a polynomial algorithm to test whether a bipartite graph is WP-free and balanced.-
dc.description.abstractP1 = v1,..., z-
dc.description.abstractP2 = v2, ..., z-
dc.description.abstractM = v,..., z, where (v1,v2,v,z) are distinct nodes, and two edges vv1 and vv2. The parachute contains no other edge except the ones mentioned above. Furthermore |E(P1)| + |E(P2)| ³ 3. A cycle C in a bipartite graph is said to be quad if its length is congruent to 0 mod 4. C is unquad if its length is congruent to 2 mod 4. In this paper we consider bipartite graphs that do not contain a wheel, a parachute and an unquad chordless cycle as induced subgraphs. These graphs are called WP-free balanced bipartite graphs and we prove the following 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 uv, and four disjoint node sets B, D, E, F such that the node sets B?D, E?F and B?E induce complete bipartite graphs KBD, KEF and KBE with the following properties: ? The removal of the edges of both KBD and KEF disconnects G. ? Node u belongs to B and v belongs to E. Furthermore the removal of the nodes in KBE disconnects G. To a 0, 1 matrix A we associate a bipartite graph G(Vr, Vc-
dc.description.abstractE) as follows: The node sets Vr and Vc represent the row set and the column set of A and edge ij belongs to E if and only if aij = 1. A 0, 1 matrix A is balanced if A does not contain a square submatrix of odd order with two ones per row and per column. Balanced matrices are important in integer programming and combinatorial optimization since the associated set packing and set covering polytopes have integral vertices. A 0, 1 matrix is balanced if and only if the associated bipartite graph does not contain an unquad chordless cycle. In this case, we say that the bipartite graph is balanced. Hence WP-free balanced bipartite graphs are a subclass of balanced bipartite graphs. The following subclasses of balanced bipartite graphs are WP-free and have been extensively studied. Totally balanced bipartite graphs are the ones not containing a chordless cycle of length greater than four. Strongly balanced bipartite graphs are the ones not containing an unquad cycle with less than two chords. The above theorem generalizes decomposition theorems for these classes of graphs and yields a polynomial algorithm to test whether a bipartite graph is WP-free and balanced. © 1995.-
dc.subjectApplied Mathematics-
dc.titleDecomposition of wheel-and-parachute-free balanced bipartite graphs-
dc.typeJournal Article-
dc.identifier.doi10.1016/0166-218X(94)00148-7-
dc.pages103-117p.-
dc.vol.noVol.62-
dc.issue.noIss.1-3-
dc.journal.nameDiscrete Applied Mathematics-
Appears in Collections:1990-1999
Files in This Item:
File SizeFormat 
Rao_DAM_1995_Vol.62_Iss.1-3.pdf1.03 MBAdobe PDFView/Open    Request a copy
Show simple item record

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.