Decomposable graphs and hypergraphs. (English) Zbl 0533.05046

Lauritzen, S. L.; Speed, T. P.; Vijayan, K.

J. Aust. Math. Soc., Ser. A 36, 12-29 (1984).

The paper starts with organizing set-theoretic properties concerning decomposability (§ 2). The authors follow S. J. Haberman [The analysis of frequency data (1974; Zbl 0325.62017)], H. G. Kellerer [Z. Wahrscheinlichkeitstheor. Verw. Geb. 3, 247-270 (1964; Zbl 0126.340)] and N. N. Vorob’ev [Theor. Probab. Appl. 12 (1967), 251-266 (1968; Zbl 0171.410)]. § 2 ends with some remarks dealing with algorithms to check decomposability. The main work begins in § 3 where it is shown that the 2-section of any decomposable hypergraph is conformed which reduces the further discussion to those decomposable hypergraphs which consist of the class of all cliques of a given graph G. A further simplification allows to consider connected graphs only. An index associated with the complete subsets of a given hypergraph H, being a graph-theoretic analogue of an index defined 10 years ago by Haberman, is introduced. The authors also show that the clique hypergraph of a graph is decomposable if and only if the graph is triangulated and characterize such graphs in terms of a combinatorial identity.

Reviewer: L.Zaremba

MSC:

05C65	Hypergraphs
05C10	Planar graphs; geometric and topological aspects of graph theory

Keywords:

clique hypergraph; triangulated graph; decomposable hypergraph

Citations:

Zbl 0325.62017; Zbl 0126.340; Zbl 0171.410