Name
Abstract | ||
|---|---|---|
A permutation w gives rise to a graph G w ; the vertices of G w are the letters in the permutation and the edges of G w are the inversions of w . We find that the number of trees among permutation graphs with n vertices is 2 n - 2 for n ¿ 2 . We then study T n , a uniformly random tree from this set of trees. In particular, we study the number of vertices of a given degree in T n , the maximum degree in T n , the diameter of T n , and the domination number of T n . Denoting the number of degree- k vertices in T n by D k , we find that ( D 1 , ¿ , D m ) converges to a normal distribution for any fixed m as n ¿ ∞ . The vertex domination number of T n is also asymptotically normally distributed as n ¿ ∞ . The diameter of T n shifted by - 2 is binomially distributed with parameters n - 3 and 1 / 2 . Finally, we find the asymptotic distribution of the maximum degree in T n , which is concentrated around log 2 n . |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.disc.2016.05.028 | Discrete Mathematics |
Keywords | Field | DocType |
Permutation graph,Permutation tree,Indecomposable permutation,Diameter,Maximum degree,Domination number | Random tree,Permutation graph,Discrete mathematics,Combinatorics,Vertex (geometry),Permutation,Cyclic permutation,Degree (graph theory),Domination analysis,Mathematics,Asymptotic distribution | Journal |
Volume | Issue | ISSN |
339 | 12 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hüseyin Acan | 1 | 6 | 1.86 |
| Pawel Hitczenko | 2 | 52 | 15.48 |
| HitczenkoPaweł | 3 | 0 | 0.34 |