Decomposable graphs and hypergraphs

Steffen L. Lauritzen; TP SPEED; K VIJAYAN

doi:10.1017/S1446788700027300

Decomposable graphs and hypergraphs

Steffen L. Lauritzen, TP SPEED, K VIJAYAN

54 Citations (Scopus)

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.

Original language	English
Journal	Journal of the Australian Mathematical Society. Series A. Pure mathematics and statistics
Volume	36
Issue number	FEB
Pages (from-to)	12-29
Number of pages	18
ISSN	0263-6115
DOIs	https://doi.org/10.1017/S1446788700027300
Publication status	Published - 1984
Externally published	Yes

Access to Document

10.1017/S1446788700027300

Cite this

@article{f637c77404904953ab1e78f4bdfcb46d,

title = "Decomposable graphs and hypergraphs",

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.",

author = "Lauritzen, {Steffen L.} and TP SPEED and K VIJAYAN",

year = "1984",

doi = "10.1017/S1446788700027300",

language = "English",

volume = "36",

pages = "12--29",

journal = "Journal of the Australian Mathematical Society. Series A. Pure mathematics and statistics",

issn = "0263-6115",

publisher = "Australian Mathematical Society",

number = "FEB",

}

TY - JOUR

T1 - Decomposable graphs and hypergraphs

AU - Lauritzen, Steffen L.

AU - SPEED, TP

AU - VIJAYAN, K

PY - 1984

Y1 - 1984

N2 - 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.

AB - 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.

U2 - 10.1017/S1446788700027300

DO - 10.1017/S1446788700027300

M3 - Journal article

SN - 0263-6115

VL - 36

SP - 12

EP - 29

JO - Journal of the Australian Mathematical Society. Series A. Pure mathematics and statistics

JF - Journal of the Australian Mathematical Society. Series A. Pure mathematics and statistics

IS - FEB

ER -