HomeIssuesEnumeration of 2-trees with directed cells

Enumeration of 2-trees with directed cells | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2026. № 71. DOI: 10.17223/20710410/71/5

We consider the problem of enumerating 2-trees with oriented cells up to isomorphism. A 2-tree is a simple graph obtained from K3 by the iterative addition of vertices connected to the ends of some edge. The cells of a 2-tree are oriented if in each cell (triangle) the vertices are independently labeled 1, 2, 3. The cells are partially oriented if one vertex is independently labeled in each cell. Using the Redfield - Polya theorem and dissymmetry lemma, we compute generating functions for the number of 2-trees with oriented and partially oriented cells.
  • Title Enumeration of 2-trees with directed cells
  • Headline Enumeration of 2-trees with directed cells
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 71
  • Date:
  • DOI 10.17223/20710410/71/5
Keywords
2-trees, Polya counting, generating functions
Authors
References
McKay В. D. and Piperno A. Practical graph isomorphism. II // J. Symbolic Comput. 2014. V.60. P. 94-112.
Xapapu Ф., Палмер Э. Перечисление графов. M.: Мир. 1977. 328 с.
Fowler Т., Gessel I. М., Labelle G., and Leroux Р. The specification of 2-trees // Adv. Appl. Math. 2002. V.28. No. 2. P. 145-168.
Labelle G., Lamathe C., and Leroux P. Labelled and unlabelled enumeration of k-gonal 2-trees // J. Combinat. Theory. Ser. A. 2004. V. 106. No. 2. P.193-219.
Gainer-Dewar A. and Gessel I. M. Counting unlabeled k-trees // J.Combinat. Theory. Ser. A. 2014. V. 126. P. 177-193.
Qian J. Enumeration of unlabeled directed hypergraphs // Electronic J.Combinatorics. 2013. V. 20. Iss.l. Article no. P46.
Qian J. Enumeration of unlabeled uniform hypergraphs // Discrete Math. 2014. V. 326. P. 6674.
Polya G. and Read R. C.H.Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds. Berlin; Heidelberg: Springer, 1987.
Ландо C.K. Лекции о производящих функциях. М.: МЦМНО, 2007. 144с.
https://github.com/VVerdenko/oriented-2-trees - Вычисление производящих функций для 3-ориентированных и частично 3-ориентированных 2-деревьев. 2025.
Enumeration of 2-trees with directed cells | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2026. № 71. DOI: 10.17223/20710410/71/5
Enumeration of 2-trees with directed cells | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2026. № 71. DOI: 10.17223/20710410/71/5
Download full-text version
Counter downloads: 41