ISSN:
1436-4646
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract A cycle of a bipartite graphG(V+, V−; E) is odd if its length is 2 (mod 4), even otherwise. An odd cycleC is node minimal if there is no odd cycleC′ of cardinality less than that ofC′ such that one of the following holds:C′ ∩V + ⊂C ∩V + orC′ ∩V − ⊂C ∩V −. In this paper we prove the following theorem for bipartite graphs: For a bipartite graphG, one of the following alternatives holds: -All the cycles ofG are even. -G has an odd chordless cycle. -For every node minimal odd cycleC, there exist four nodes inC inducing a cycle of length four. -An edge (u, v) ofG has the property that the removal ofu, v and their adjacent nodes disconnects the graphG. To every (0, 1) matrixA we can associate a bipartite graphG(V+, V−; E), whereV + andV − represent respectively the row set and the column set ofA and an edge (i,j) belongs toE if and only ifa ij = 1. The above theorem, applied to the graphG(V+, V−; E) can be used to show several properties of some classes of balanced and perfect matrices. In particular it implies a decomposition theorem for balanced matrices containing a node minimal odd cycleC, having the property that no four nodes ofC induce a cycle of length 4. The above theorem also yields a proof of the validity of the Strong Perfect Graph Conjecture for graphs that do not containK 4−e as an induced subgraph.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01589107
Permalink
