On random trees obtained from permutation graphs

Abstract: A permutation

gives rise to a graph

; the vertices of

are the letters in the permutation and the edges of

are the inversions of

. We find that the number of trees among permutation graphs with

n

vertices is

2^{n - 2}

for

n g e 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 o t s, D_{m})

converges to a normal distribution for any fixed

m

as

n o i n f t y

. The vertex domination number of

T_{n}

is also asymptotically normally distributed as

n o i n f t y

. 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

l o g_{2} n

.

Recommendations

Cites work

Cited in

(3)

Describes a project that uses

Uses Software

This page was built for publication: On random trees obtained from permutation graphs