Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418041 | Discrete Applied Mathematics | 2015 | 6 Pages |
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
Lilian Markenzon, Christina Fraga Esteves Maciel Waga,