Journal of the Australian Mathematical Society (Series A)

Research Article

Almost all chordal graphs split

E. A. Bendera1, L. B. Richmonda2 and N. C. Wormalda3

a1 Department of Mathematics University of California at San Diego La Jolla, California 92093, USA

a2 Department of Combinatorics and Optimization University of Waterloo Waterloo, Ontario N2L 3G1, Canada

a3 Department of Mathematics, Statistics and Computer Science University of Newcastle New South Wales 2308, Australia

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.

(Received July 25 1983)

1980 Mathematics subject classification (Amer. Math. Soc.)

  • 05 C 99