New results on ptolemaic graphs

详细信息    查看全文

• 作者：Lilian Markenzon^a ; ^{markenzon@nce.ufrj.br" class="auth_mail" title="E-mail the corresponding author} ; ^{limarkenzon@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Christina Fraga Esteves Maciel Waga^b ; ^{waga@ime.uerj.br" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Ptolemaic graph ; Minimal vertex separator ; Block duplicate graph ; AC graph ; Laminar chordal graph
• 刊名：Discrete Applied Mathematics
• 出版年：2015
• 出版时间：11 December 2015
• 年：2015
• 卷：196
• 期：Complete
• 页码：135-140
• 全文大小：387 K

文摘

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.