Transchordal graphs (Q1567619): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q593309 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Heinz Joachim Presia / rank | |||
Normal rank |
Revision as of 00:57, 20 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Transchordal graphs |
scientific article |
Statements
Transchordal graphs (English)
0 references
21 June 2000
0 references
It is known that chordal graphs are intersection graphs of connected subgraphs of trees. They can be extended to the family of transchordal graphs by replacing tree representations with circuit bases. The exact formal definition by using three conditions (intersection, circuit and cover condition) linking a transchordal graph to its graph-and-circuit-basis representation in order to extend what happens for chordal graphs is given in Section 2. For it the notions of host graph, guest graph and host pair for a guest graph are introduced. In Theorem 1 it is proved that every transchordal graph has a special host pair, a so-called \({\mathfrak C}\)-host pair. In Section 3 the structure of these \({\mathfrak C}\)-host pairs and with it the connection between guest transchordal graph and the host representation are investigated and it is shown how \({\mathfrak C}\)-hosts generalize the notion of clique trees for chordal graphs. In Section 4 a basic construction of these host representations is described. It is proved how the basic construction produces \({\mathfrak C}\)-hosts for transchordal graphs (Theorem 5). In the final section, Section 5, Theorem 6 gives a combinatorial characterization of transchordal graphs that resembles two previous characterizations of chordal graphs.
0 references
chordal graphs
0 references
intersection graphs
0 references
trees
0 references
transchordal graphs
0 references
representations
0 references
host graph
0 references
guest graph
0 references
host pair
0 references
clique trees
0 references