Graphical properties related to minimal imperfection |
| |
Authors: | RG Bland H-C Huang LE Trotter |
| |
Institution: | School of OR/IE, Cornell University, USA;Dept. of Economics and Statistics, Nanyang University, Singapore;School of OR/IE, Cornell University, USA and Institut für Ökonometrie und O.R. Universität Bonn, West Germany |
| |
Abstract: | Say that graph G is partitionable if there exist integers α?2, ω? 2, such that |V(G)| ≡ αω + 1 and for every υ?V(G) there exist partitions of V(G)\ υ into stable sets of size α and into eliques of size ω. An immediate consequence of Lovász' characterization of perfect graphs is that every minimal imperfect graph G is partitionable with α ≡ α (G) andω ≡ ω(G).Padberg has shown that in every minimal imperfect graph G the cliques and stable sets of maximum size satisfy a series of conditions that reflect extraordinary symmetry G. Among these conditions are: the number of cliques of size ω(G) is exactly |V(G)|; the number of stable sets of size α(G) is exactly |V(G)|: every vertex of G is contained in exactly ω(G) cliques of size ω(G) and α(G) stable sets of size α(G): for every clique Q (respectively, stable set S) of maximum size there is a unique stable set S (clique O) of maximum size such that Q∩S ≡ Ø.Let Cnk denote the graph whose vertices can be enumerated as υ1,…,υn in such a way that υ1 and υ1 are adjacent in G if and only if i and j differ by at most k, modulo n. Chvátal has shown that Berge's Strong Perfect graph Conjecture is equivalent to the conjecture that if G is minimal imperfect with α(G) ≡ αandω(G) ≡ ω, then G has a spanning subgraph isomorphic to Cαω+1ω. Padberg's conditions are sufficiently restrictive to suggest the possibility of establishing the Strong Perfect Graph Conjecture by proving that any graph G satisfying these conditions must contain a spanning subgraph isomorphic to Cαω+1ω, whereα(G) ≡ αandω(G) ≡ ω. It is shown here, using only elementary linear algebra, that all partitionable graphs satisfy Padberg's conditions, as well as additional properties of the same spirit. Then examples are provided of partitionable graphs which contain no spanning subgraph isomorphic to Cαω+1ω, whereα(G) ≡ α and ω(G) ≡ ω. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|