A Class of Facet Producing Graphs for Vertex Packing Polyhedra.
Technical summary rept.,
WISCONSIN UNIV MADISON MATHEMATICS RESEARCH CENTER
Pagination or Media Count:
The author examines a family F of regular graphs which properly generalizes cliques, holes and anti-holes. A characterization is given for members of F whose associated vertex packing polytope contains a facet which cannot be derived from any proper induced subgraph. Simple necessary and sufficient conditions are given for a graph in F to contain another as an induced subgraph these conditions are used to show that the graphs in F satisfy the Strong Perfect Graph Conjecture. Complements of members of F are also studied and we show that if both a graph and its complement belong to F, then the graph is an odd hole or odd anti-hole. Author
- Theoretical Mathematics