Enumeration of P4-free chordal graphs

Robert Castelo; Nick Wormald

doi:10.1007/s00373-002-0513-9

Enumeration of P₄-free chordal graphs

Robert Castelo, Nick Wormald

Research output: Contribution to journal › Article › Research › peer-review

8 Citations (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	467-474
Number of pages	8
Journal	Graphs and Combinatorics
Volume	19
Issue number	4
DOIs	https://doi.org/10.1007/s00373-002-0513-9
Publication status	Published - 2003
Externally published	Yes

Access to Document

10.1007/s00373-002-0513-9

Cite this

@article{ac9cb6edae704424be6a46d3948530b3,

title = "Enumeration of P4-free chordal graphs",

abstract = "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.",

author = "Robert Castelo and Nick Wormald",

year = "2003",

doi = "10.1007/s00373-002-0513-9",

language = "English",

volume = "19",

pages = "467--474",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer-Verlag London Ltd.",

number = "4",

}

TY - JOUR

T1 - Enumeration of P4-free chordal graphs

AU - Castelo, Robert

AU - Wormald, Nick

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0346937588

U2 - 10.1007/s00373-002-0513-9

DO - 10.1007/s00373-002-0513-9

M3 - Article

AN - SCOPUS:0346937588

SN - 0911-0119

VL - 19

SP - 467

EP - 474

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 4

ER -

Enumeration of P4-free chordal graphs

Abstract

Access to Document

Other files and links

Cite this

Enumeration of P₄-free chordal graphs