k-separator chordal graphs: leafage and subfamilies

被引：0

作者：

Markenzon, Lilian ^{[1
]}

da Costa Pereira, Paulo Renato ^{[2
]}

Waga, Christina F. E. M. ^{[3
]}

机构：

[1] Univ Fed Rio de Janeiro, NCE, Rio De Janeiro, Brazil

[2] Dept Policia Fed, Brasilia, DF, Brazil

[3] Univ Estado Rio de Janeiro, IME, BR-20550011 Rio De Janeiro, Brazil

来源：

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH | 2013年 / 20卷 / 05期

关键词：

chordal graph; minimal vertex separator; leafage; k-sep chordal graph; k-caterpillar; MINIMAL VERTEX SEPARATORS; TIME ALGORITHM; SUBCLASSES; TREES;

D O I：

10.1111/j.1475-3995.2012.00875.x

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

The leafage of a chordal graph G is the minimum number of leaves among the clique-trees of G. In this paper, based on properties of the minimal vertex separators, the leafage of a k-separator chordal graph is determined in linear time. This result allows establishment of the relationship of some subfamilies of chordal graphs, such as k-trees, interval and uniquely representable chordal graphs.

引用

页码：681 / 688

页数：8

共 18 条

[1] Alcon L., 2011, ELECT NOTES DISCRETE, V37, P81
[2] Blair J.R.S., 1993, IMA Math. Appl., V56, P1
[3] A linear time algorithm to list the minimal separators of chordal graphs
Chandran, LS
Grandoni, F
[J]. DISCRETE MATHEMATICS, 2006, 306 (03) : 351 - 358
[4] Golumbic M.C., 2004, Algorithmic Graph Theory and Perfect Graphs
[5] Habib M, 2009, LECT NOTES COMPUT SC, V5757, P290, DOI 10.1007/978-3-642-04128-0_27
[6] Hara H., 2006, 200641 METR U TOK DE
[7] Minimal vertex separators of chordal graphs
Kumar, PS
Madhavan, CEV
[J]. DISCRETE APPLIED MATHEMATICS, 1998, 89 (1-3) : 155 - 168
[8] Clique tree generalization and new subclasses of chordal graphs
Kumar, PS
Madhavan, CEV
[J]. DISCRETE APPLIED MATHEMATICS, 2002, 117 (1-3) : 109 - 131
[9] Lin I., 1998, Discuss. Math. Graph Theory, V18, P23
[10] Subclasses of k-trees:: Characterization and recognition
Markenzon, L
Justel, CM
Paciornik, N
[J]. DISCRETE APPLIED MATHEMATICS, 2006, 154 (05) : 818 - 825

← 1 2 →