MAXCLIQUE AND UNIT DISK CHARACTERIZATIONS OF STRONGLY CHORDAL GRAPHS

被引：2
作者：
De Caria, Pablo [1 ]
McKee, Terry A. [2 ]
机构：
[1] Univ Nacl La Plata, CONICET, Dept Matemat, La Plata, Buenos Aires, Argentina
[2] Wright State Univ, Dept Math & Stat, Dayton, OH 45435 USA
来源：
DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2014年 / 34卷 / 03期
关键词：
chordal graph; strongly chordal graph; clique; maxclique; closed neighborhood;
D O I：
10.7151/dmgt.1757
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
Maxcliques (maximal complete subgraphs) and unit disks (closed neighborhoods of vertices) sometime play almost interchangeable roles in graph theory. For instance, interchanging them makes two existing characterizations of chordal graphs into two new characterizations. More intriguingly, these characterizations of chordal graphs can be naturally strengthened to new characterizations of strongly chordal graphs
引用
收藏
页码：593 / 602
页数：10
相关论文
共 13 条
[1]   Dually chordal graphs [J].
Brandstadt, A ;
Dragan, F ;
Chepoi, V ;
Voloshin, V .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1998, 11 (03) :437-+
[2]  
Brandstadt A., 1999, SIAM MONOGR DISCRET
[3]   On the correspondence between tree representations of chordal and dually chordal graphs [J].
De Caria, Pablo ;
Gutierrez, Marisa .
DISCRETE APPLIED MATHEMATICS, 2014, 164 :500-511
[4]   On minimal vertex separators of dually chordal graphs: Properties and characterizations [J].
De Caria, Pablo ;
Gutierrez, Marisa .
DISCRETE APPLIED MATHEMATICS, 2012, 160 (18) :2627-2635
[5]   CHARACTERIZATIONS OF STRONGLY CHORDAL GRAPHS [J].
FARBER, M .
DISCRETE MATHEMATICS, 1983, 43 (2-3) :173-189
[6]  
McKee T.A., 2011, DISCUSS MATH GRAPH T, V31, P577, DOI 10.7151/dmgt.1566
[7]  
McKee T.A, 1993, B ICA, V9, P27
[8]  
McKee T.A., 2008, C NUMER, V191, P213
[9]  
McKee T. A., 1999, SIAM MONOG DISCR MAT
[10]   A new characterization of strongly chordal graphs [J].
McKee, TA .
DISCRETE MATHEMATICS, 1999, 205 (1-3) :245-247
12