Transchordal graphs (Q1567619): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q126465047 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0012-365x(99)00378-7 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2914587322 / rank | |||
Normal rank |
Latest revision as of 11:14, 30 July 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