Almost all chordal graphs split
- 1 February 1985
- journal article
- research article
- Published by Cambridge University Press (CUP) in Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics
- Vol. 38 (2) , 214-221
- https://doi.org/10.1017/s1446788700023077
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.Keywords
This publication has 5 references indexed in Scilit:
- Algorithmic Aspects of Vertex Elimination on GraphsSIAM Journal on Computing, 1976
- A characterisation of rigid circuit graphsDiscrete Mathematics, 1974
- The intersection graphs of subtrees in trees are exactly the chordal graphsJournal of Combinatorial Theory, Series B, 1974
- Triangulated graphs and the elimination processJournal of Mathematical Analysis and Applications, 1970
- On rigid circuit graphsAbhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, 1961