Previous |  Up |  Next


connected chordal graph; ternary system
By a chordal graph is meant a graph with no induced cycle of length $\ge 4$. By a ternary system is meant an ordered pair $(W, T)$, where $W$ is a finite nonempty set, and $T \subseteq W \times W \times W$. Ternary systems satisfying certain axioms (A1)–(A5) are studied in this paper; note that these axioms can be formulated in a language of the first-order logic. For every finite nonempty set $W$, a bijective mapping from the set of all connected chordal graphs $G$ with $V(G) = W$ onto the set of all ternary systems $(W, T)$ satisfying the axioms (A1)–(A5) is found in this paper.
[1] G. Chartrand and L. Lesniak: Graphs & Digraphs. Third edition. Chapman & Hall, London, 1996. MR 1408678
[2] R. Diestel: Graph Theory. Second Edition. Graduate Texts in Mathematics 173. Springer, New York, 2000. MR 1743598 | Zbl 0957.05001
[3] G. A. Dirac: On rigid circuit graphs. Abh. Math. Univ. Hamburg 25 (1961), 71–76. DOI 10.1007/BF02992776 | MR 0130190 | Zbl 0098.14703
[4] L. Nebeský: Signpost systems and connected graphs. Czech. Math. J. 55 (2005), 283–293. DOI 10.1007/s10587-005-0022-0 | MR 2137138
Partner of
EuDML logo