×
Hofer-Temmel, Christoph; Lehner, Florian

Clique trees of infinite locally finite chordal graphs. (English) Zbl 1391.05186

Electron. J. Comb. 25, No. 2, Research Paper P2.9, 15 p. (2018).
Summary: We investigate clique trees of infinite locally finite chordal graphs. Our main contribution is a bijection between the set of clique trees and the product of local finite families of finite trees. Even more, the edges of a clique tree are in bijection with the edges of the corresponding collection of finite trees. This allows us to enumerate the clique trees of a chordal graph and extend various classic characterisations of clique trees to the infinite setting.

Cited in 1 Document

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
05C05 Trees
05C30 Enumeration in graph theory

Keywords:

graph theory; chordal graphs; infinite graphs; clique trees
Cite Review PDF
Full Text: arXiv Link

References:

[1] Catriel Beeri, Ronald Fagin, David Maier, and Mihalis Yannakakis. On the desirability of acyclic database schemes. J. Assoc. Comput. Mach., 30(3):479-513, 1983. ISSN 0004-5411.doi:10.1145/2402.322389. · Zbl 0624.68087
[2] Philip A. Bernstein and Nathan Goodman. Power of natural semijoins. SIAM J. Comput., 10(4):751-771, 1981. ISSN 0097-5397.doi:10.1137/0210059. · Zbl 0469.68090
[3] Jean R. S. Blair and Barry Peyton. An introduction to chordal graphs and clique trees. In Graph theory and sparse matrix computation, volume 56 of IMA Vol. Math. Appl., pages 1-29. Springer, New York, 1993.doi:10.1007/978-1-4613-8369-7 1. · Zbl 0803.68081
[4] Reinhard Diestel.Graph theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, third edition, 2005. ISBN 978-3-540-26182-7; 3-540-26182 6; 978-3-540-26183-4. · Zbl 1074.05001
[5] G. A. Dirac. On rigid circuit graphs. Abh. Math. Sem. Univ. Hamburg, 25:71-76, 1961. ISSN 0025-5858. · Zbl 0098.14703
[6] Philippe Galinier, Michel Habib, and Christophe Paul. Chordal graphs and their clique graphs. In Graph-theoretic concepts in computer science (Aachen, 1995), vol ume 1017 of Lecture Notes in Comput. Sci., pages 358-371. Springer, Berlin, 1995. doi:10.1007/3-540-60618-1 88. · Zbl 1533.05224
[7] F˘anic˘a Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Combinatorial Theory Ser. B, 16:47-56, 1974. · Zbl 0266.05101
[8] R. Halin. On the representation of triangulated graphs in trees. European J. Combin., 5(1):23-28, 1984. ISSN 0195-6698. · Zbl 0541.05049
[9] Chin Wen Ho and R. C. T. Lee. Counting clique trees and computing perfect elimina tion schemes in parallel. Inform. Process. Lett., 31(2):61-68, 1989. ISSN 0020-0190. · Zbl 0685.68050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.