Almost all chordal graphs split

E. A. Bender, L. B. Richmond, N. C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

38 Citations (Scopus)

Abstract

A chordal graph is a graph in which every cycle of length at least 4 has a chord. If G is a random n-vertex labelled chordal graph, the size of the larget clique in about n/2 and deletion of this clique almost surely leaves only isolated vertices. This gives the asymptotic number of chordal graphs and information about a variety of things such as the size of the largest clique and connectivity.

Original languageEnglish
Pages (from-to)214-221
Number of pages8
JournalJournal of the Australian Mathematical Society
Volume38
Issue number2
DOIs
Publication statusPublished - 1985
Externally publishedYes

Cite this