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 .
['Hüseyin Acan', 'Pawel Hitczenko']
On random trees obtained from permutation graphs