Minimum proper interval graphs

✍ Scribed by M. Gutierrez; L. Oubiña

• Book ID: 103061091
• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 546 KB
• Volume: 142
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00007-j

✦ Synopsis

A graph G is a proper interval graph if there exists a mapping r from V(G) to the class of closed intervals of the real line with the properties that for distinct vertices u and w we have r(u) n r(w) # 0 if and only if u and w are adjacent and neither of the intervals r(u), r(w) contain the other. We prove that for every proper interval graph G, 1 V(G)1 > 2 c(G) -c(K(G)), where c(G) is the number of cliques of G and K(G) is the clique graph of G. If the equality is verified we call G a minimum proper inter& graph. The main result is that the restriction to the class of minimum proper interval graphs of clique mapping G -+ K(G) is a bijection (up to isomorphism) onto the class of proper interval graphs. We find the greatest clique-closed class I: (K(Z) = Z) contained in the union of the class of connected minimum proper interval graphs and the class of complete graphs. We enumerate the minimum proper interval graphs with n vertices.