Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-23T13:53:41.480Z Has data issue: false hasContentIssue false

Almost all chordal graphs split

Published online by Cambridge University Press:  09 April 2009

E. A. Bender
Affiliation:
Department of Mathematics University of California at San DiegoLa Jolla, California 92093, USA
L. B. Richmond
Affiliation:
Department of Combinatorics and Optimization University of WaterlooWaterloo, Ontario N2L 3G1, Canada
N. C. Wormald
Affiliation:
Department of Mathematics, Statistics and Computer Science University of NewcastleNew South Wales 2308, Australia
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 1985

References

[1]Buneman, P., ‘A characterisation of rigid circuit graphs’, Discrete Math. 9 (1974), 205212.CrossRefGoogle Scholar
[2]Dirac, G. A., ‘On rigid circuit graphs’, Abh. Math. Sem. Univ. Hamburg 25 (1961), 7176.CrossRefGoogle Scholar
[3]Erdös, P., Kleitman, D. J. and Rothschild, B. L., Asymptotic enumeration of Kn-free graphs, Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973), Tomo II. Atti dei Convegni Lincei, No. 17 (1976), 1927.Google Scholar
[4]Gavril, F., ‘The intersection graphs of subtrees in trees are exactly the chordal graphs’, J. Combin. Theory Ser. B 16 (1974), 4756.CrossRefGoogle Scholar
[5]Rose, D. J., ‘Triangulated graphs and the elimination process’, J. Math. Anal. Appl. 32 (1970), 597609.CrossRefGoogle Scholar
[6]Rose, D. J., Tarjan, R. E. and Lueker, G. S., ‘Algorithmic aspects of vertex elimination on graphs’, SIAM J. Comput. 5 (1976), 266283.CrossRefGoogle Scholar