Minimum proper interval graphs (Q1896346)

A graph \(G= (V, E)\) is a proper interval graph, if we can associate to each vertex \(v\) in interval \(I_v\) on the real line, such that no such interval is a subset of another such interval, and for all distinct vertices \(v\), \(w\) we have \((v, w)\in V\), if and only if \(I_v\) and \(I_w\) intersect. The number of cliques of a graph \(G\) is denoted by \(c(G)\). The clique graph of a graph \(G\), denoted by \(K(G)\), has as vertices the cliques of \(G\), vertices representing cliques are made adjacent when the cliques intersect. In this paper, it first is shown that for every proper interval graph \(G= (V, E)\) we have \(|V|\geq 2c(G)- c(K(G))\). A proper interval graph \(G= (V, E)\) is said to be minimum, whenever \(|V|= 2c(G)- c(K(G))\). The main result of this paper is that the mapping \(K\) (mapping graphs to their clique graphs), when restricted to minimum proper interval graphs, is a bijection (up to isomorphism) onto the class of proper interval graphs, i.e., the clique graph of a minimum proper interval graph is a proper interval graph, and every proper interval graph is the clique graph of a minimum proper interval graph, which is unique up to isomorphism. A class of graphs \(\Pi\) is clique-closed, if \(\{K(G)\mid G\in \Pi\}= \Pi\). The authors give a simple characterization of the greatest clique-closed class, contained in \(\Pi\). They finally show how to enumerate the minimum proper interval graphs.