A Class of Facet Producing Graphs for Vertex Packing Polyhedra.
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1974
- Accession Number
- AD0784021
Entities
People
- L. E. Trotter Jr.
Organizations
- University of Wisconsin–Madison