Decomposable graphs and hypergraphs
Open Access
- 1 February 1984
- journal article
- research article
- Published by Cambridge University Press (CUP) in Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics
- Vol. 36 (1), 12-29
- https://doi.org/10.1017/s1446788700027300
Abstract
We define and investigate the notion of a decomposable hypergraph, showing that such a hypergraph always is conformal, that is, can be viewed as the class of maximal cliques of a graph. We further show that the clique hypergraph of a graph is decomposable if and only if the graph is triangulated and characterise such graphs in terms of a combinatorial identity.Keywords
This publication has 20 references indexed in Scilit:
- Minimal triangulation of a graph and optimal pivoting order in a sparse matrixJournal of Mathematical Analysis and Applications, 1976
- The Analysis of Frequency DataPublished by JSTOR ,1975
- An algorithm for testing chordality of graphsInformation Processing Letters, 1975
- The intersection graphs of subtrees in trees are exactly the chordal graphsJournal of Combinatorial Theory, Series B, 1974
- Partitioning of Chi-Square, Analysis of Marginal Contingency Tables, and Estimation of Expected Frequencies in Multidimensional Contingency TablesJournal of the American Statistical Association, 1971
- Partitioning of Chi-Square, Analysis of Marginal Contingency Tables, and Estimation of Expected Frequencies in Multidimensional Contingency TablesJournal of the American Statistical Association, 1971
- Triangulated graphs and the elimination processJournal of Mathematical Analysis and Applications, 1970
- Incidence matrices and interval graphsPacific Journal of Mathematics, 1965
- Markov Measures and Markov ExtensionsTheory of Probability and Its Applications, 1963
- On rigid circuit graphsAbhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, 1961