Conference Paper

On Noncrossing and Plane Tree-Like Structures

Volume: 4 Number: 2 June 30, 2021
Isaac Owino Okoth *
PDF Download
Communications in Advanced Mathematical Sciences Cover Communications in Advanced Mathematical Sciences
EN

On Noncrossing and Plane Tree-Like Structures

Abstract

Mathematical trees are connected graphs without cycles, loops and multiple edges. Various trees such as Cayley trees, plane trees, binary trees, $d$-ary trees, noncrossing trees among others have been studied extensively. Tree-like structures such as Husimi graphs and cacti are graphs which posses the conditions for trees if, instead of vertices, we consider their blocks. In this paper, we use generating functions and bijections to find formulas for the number of noncrossing Husimi graphs, noncrossing cacti and noncrossing oriented cacti. We extend the work to obtain formulas for the number of bicoloured noncrossing Husimi graphs, bicoloured noncrossing cacti and bicoloured noncrossing oriented cacti. Finally, we enumerate plane Husimi graphs, plane cacti and plane oriented cacti according to number of blocks, block types and leaves.

Keywords

noncrossing tree , plane trees , tree-like structure , Husimi graph , cactus , enumeration

References

  1. [1] M. B´ona, M. Bousquet, G. Labelle, P. Leroux, Enumeration of m-ary cacti, Adv. Appl. Math., 24 (1) (2000), 22-56.
  2. [2] P. Flajolet, M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204 (1-3) (1999), 203-229.
  3. [3] G. W. Ford, G. E. Uhlenbeck, Combinatorial Problems in the Theory of Graphs, I, Proc. Nat. Acad. Sciences, 42 (1956), 122-128.
  4. [4] F. Harary, G. E. Uhlenbeck, On the number of Husimi trees, Proc. Nat. Aca. Sci., 39 (1953), 315-322.
  5. [5] K. Husimi, Note on Mayers’ theory of cluster integrals, J. Chem. Phys., 18 (1950), 682-684.
  6. [6] S. Kim, S. Seo, H. Shin, Refined enumeration of vertices among all rooted rooted d-trees, (2018), arXiv:1806.06417.
  7. [7] P. Leroux. Enumerative problems inspired by Mayer’s theory of cluster integrals, Electron. J. Combin., 11 (2004).
  8. [8] J. E. Mayer, Equilibrium Statistical Mechanics, The international encyclopedia of physical chemistry and chemical physics, Pergamon Press, Oxford, 1968.
  9. [9] M. Noy, Enumeration of noncrossing trees on a circle, Discrete Math., 180 (1-3) (1998), 301-313.
  10. [10] I. O. Okoth, Combinatorics of oriented trees and tree-like structures, PhD Thesis, Stellenbosch University, 2015.

Details

Primary Language

English

Subjects

Mathematical Sciences

Journal Section

Conference Paper

Authors

Publication Date

June 30, 2021

Submission Date

September 30, 2020

Acceptance Date

June 14, 2021

Published in Issue

Year 2021 Volume: 4 Number: 2

DOI

https://doi.org/10.33434/cams.803065

IZ

https://izlik.org/JA22WS94JK

Cite

RIS / Bibtex
APA
Okoth, I. O. (2021). On Noncrossing and Plane Tree-Like Structures. Communications in Advanced Mathematical Sciences, 4(2), 89-99. https://doi.org/10.33434/cams.803065
AMA
1.Okoth IO. On Noncrossing and Plane Tree-Like Structures. Communications in Advanced Mathematical Sciences. 2021;4(2):89-99. doi:10.33434/cams.803065
Chicago
Okoth, Isaac Owino. 2021. “On Noncrossing and Plane Tree-Like Structures”. Communications in Advanced Mathematical Sciences 4 (2): 89-99. https://doi.org/10.33434/cams.803065.
EndNote
Okoth IO (June 1, 2021) On Noncrossing and Plane Tree-Like Structures. Communications in Advanced Mathematical Sciences 4 2 89–99.
IEEE
[1]I. O. Okoth, “On Noncrossing and Plane Tree-Like Structures”, Communications in Advanced Mathematical Sciences, vol. 4, no. 2, pp. 89–99, June 2021, doi: 10.33434/cams.803065.
ISNAD
Okoth, Isaac Owino. “On Noncrossing and Plane Tree-Like Structures”. Communications in Advanced Mathematical Sciences 4/2 (June 1, 2021): 89-99. https://doi.org/10.33434/cams.803065.
JAMA
1.Okoth IO. On Noncrossing and Plane Tree-Like Structures. Communications in Advanced Mathematical Sciences. 2021;4:89–99.
MLA
Okoth, Isaac Owino. “On Noncrossing and Plane Tree-Like Structures”. Communications in Advanced Mathematical Sciences, vol. 4, no. 2, June 2021, pp. 89-99, doi:10.33434/cams.803065.
Vancouver
1.Isaac Owino Okoth. On Noncrossing and Plane Tree-Like Structures. Communications in Advanced Mathematical Sciences. 2021 Jun. 1;4(2):89-9. doi:10.33434/cams.803065

Creative Commons License   The published articles in CAMS are licensed under a Creative Commons Attribution-NonCommercial 4.0 International License..