Abstract: | A graph is normal if there exists a cross-intersecting pair of set families one of which consists of cliques while the other one consists of stable sets, and furthermore every vertex is obtained as one of these intersections. It is known that perfect graphs are normal. Korner and de Simone observed that C5, C7 and complement of C7 are minimal, not normal and conjectured, as generalization of the Strong Perfect Graph Theorem, that every (C5, C7, complement of C7)-free graph is normal (Normal Graph Conjecture). In this paper we prove this conjecture for the class of minimal unbreakable graphs.
As it turns out, unbreakable graphs find natural applications to wireless network security. These applications, detailed in ([15], [22], [24]), range from increasing network resilience, to enhancing confidentiality, to reducing interference. An intriguing new development, documented in ([11], [12], [14], [18]), show direct relevance of unbreakable graphs to social and peer-to-peer networks. |
