Enumeration of P4-free chordal graphs

被引：4

作者：

Castelo, R

Wormald, N

机构：

[1] Pompeu Fabra Univ, Biomed Informat Grp GRIB, Barcelona 08003, Spain

[2] Univ Melbourne, Dept Math & Stat, Melbourne, Vic 3010, Australia

[3] CWI, Amsterdam, Netherlands

[4] Univ Utrecht, NL-3508 TC Utrecht, Netherlands

来源：

GRAPHS AND COMBINATORICS | 2003年 / 19卷 / 04期

关键词：

D O I：

10.1007/s00373-002-0513-9

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We count labelled chordal graphs with no induced path of length 3, both exactly and asymptotically. These graphs correspond to rooted trees in which no vertex has exactly one child, and each vertex has been expanded to a clique. Some properties of random graphs of this type are also derived. The corresponding unlabelled graphs are in 1-1 correspondence with unlabelled rooted trees on the same number of vertices.

引用

页码：467 / 474

页数：8

共 11 条

[1] ASYMPTOTIC METHODS IN ENUMERATION
BENDER, EA
[J]. SIAM REVIEW, 1974, 16 (04) : 485 - 515
[2] CANFIELD ER, 1984, J COMB THEORY A, V37, P348
[3] A characterization of moral transitive acyclic directed graph Markov models as labeled trees
Castelo, R
Siebes, A
[J]. JOURNAL OF STATISTICAL PLANNING AND INFERENCE, 2003, 115 (01) : 235 - 259
[4] TRIVIALLY PERFECT GRAPHS
GOLUMBIC, MC
[J]. DISCRETE MATHEMATICS, 1978, 24 (01) : 105 - 107
[5] Harary F., 1973, GRAPHICAL ENUMERATIO
[6] ON AN ASYMPTOTIC METHOD IN ENUMERATION
MEIR, A
MOON, JW
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 1989, 51 (01) : 77 - 89
[7] MEIR A, 1989, J COMB THEORY A, V52, P163
[8] Wilf H. S., 1990, GENERATINGFUNCTIONOL
[9] A NOTE ON COMPARABILITY GRAPH OF A TREE
WOLK, ES
[J]. PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1965, 16 (01) : 17 - &
[10] Wolk ES., 1962, P AM MATH SOC, V13, P789, DOI DOI 10.1090/S0002-9939-1962-0172273-0

← 1 2 →