Minimum proper interval graphs
type: Item
instance of: scholarly article
title: Minimum proper interval graphs
zbMATH Open document ID: 0828.05053
DOI: 10.1016/0012-365X(95)00007-J
author: Yanyan Li
published in: Discrete Mathematics
publication date: 1995-12-18T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 790751
zbMATH Keywords: enumeration
zbMATH Keywords: proper interval graph
zbMATH Keywords: interval
zbMATH Keywords: number of cliques
zbMATH Keywords: clique graph
zbMATH Keywords: characterization
zbMATH Keywords: greatest clique-closed class
reviewed by: Hans L. Bodlaender
MaRDI profile type: Publication
cites work: Parallel concepts in graph theory
cites work: Clique graphs of time graphs
cites work: On time graphs
cites work: On nontransitive indifference
cites work: On the compatibility between a graph and a simple order
description: scientific article; zbMATH DE number 790751