Decomposition of Balanced Matrices. Part 6. Even Wheels
Abstract
In this part, we prove that if a balanced bipartite graph G contains an even wheel as an induced subgraph, then it has an extended star cutset. The proof is divided into two parts, treated in Sections 2 and 3 respectively. In Section 2, we give properties of the strongly adjacent nodes to even wheels. In particular, for an even wheel (W,v) with the smallest number of spokes and, subject to this, the smallest number of nodes, we prove that at least two nodes of W, say w sub 1 and w sub 2, are adjacent to all nodes with more than two neighbors in W. In Section 3, we prove that, for the above choice of W and an appropriate choice of v, the nodes with more than two neighbors in W together with the nodes of N(v) form an extended star cutset of G.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1991
- Accession Number
- ADA247399
Entities
People
- Gérard Cornuéjols
- M. R. Rao
- Michele Conforti
Organizations
- Carnegie Mellon University