Journal article
On random trees obtained from permutation graphs
Discrete mathematics, v 339(12), pp 2871-2883
06 Dec 2016
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
A permutation w gives rise to a graph Gw; the vertices of Gw are the letters in the permutation and the edges of Gw are the inversions of w. We find that the number of trees among permutation graphs with n vertices is 2n−2 for n≥2. We then study Tn, a uniformly random tree from this set of trees. In particular, we study the number of vertices of a given degree in Tn, the maximum degree in Tn, the diameter of Tn, and the domination number of Tn. Denoting the number of degree-k vertices in Tn by Dk, we find that (D1,…,Dm) converges to a normal distribution for any fixed m as n→∞. The vertex domination number of Tn is also asymptotically normally distributed as n→∞. The diameter of Tn shifted by −2 is binomially distributed with parameters n−3 and 1/2. Finally, we find the asymptotic distribution of the maximum degree in Tn, which is concentrated around log2n.
Metrics
Details
- Title
- On random trees obtained from permutation graphs
- Creators
- Hüseyin Acan - Monash UniversityPaweł Hitczenko - Drexel University
- Publication Details
- Discrete mathematics, v 339(12), pp 2871-2883
- Publisher
- Elsevier
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Mathematics
- Web of Science ID
- WOS:000382342000003
- Scopus ID
- 2-s2.0-84977117482
- Other Identifier
- 991019168288604721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Mathematics