Article ID Journal Published Year Pages File Type
418041 Discrete Applied Mathematics 2015 6 Pages PDF
Abstract

In this paper, we analyze ptolemaic graphs for their properties as chordal graphs. First, two characterizations of ptolemaic graphs are proved. The first one is based on the reduced clique graph, a structure that was defined by Habib and Stacho (Habib and Stacho, 2012). In the second one, we simplify the characterization presented by Uehara and Uno (Uehara and Uno, 2009) with a new proof. Then, known subclasses of ptolemaic graphs are reviewed in terms of minimal vertex separators. We also define another subclass, the laminar chordal graphs, and we show that a hierarchy of ptolemaic graphs can be built based on characteristics of the minimal vertex separators in each subclass.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,