On random trees obtained from permutation graphs

详细信息    查看全文

• 作者：Hü ; seyin Acan^a ; ^{huseyin.acan@rutgers.edu" class="auth_mail" title="E-mail the corresponding author} ; Paweł Hitczenko^b ; ^{phitczen@math.drexel.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Permutation graph ; Permutation tree ; Indecomposable permutation ; Diameter ; Maximum degree ; Domination number
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 December 2016
• 年：2016
• 卷：339
• 期：12
• 页码：2871-2883
• 全文大小：475 K

文摘

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$n$ vertices is 2ⁿ⁻²$2^{n-2}$ for n≥2$n\ge 2$. We then study c801d93abe2" title="Click to view the MathML source">T_n$T_n$, a uniformly random tree from this set of trees. In particular, we study the number of vertices of a given degree in c801d93abe2" title="Click to view the MathML source">T_n$T_n$, the maximum degree in c801d93abe2" title="Click to view the MathML source">T_n$T_n$, the diameter of c801d93abe2" title="Click to view the MathML source">T_n$T_n$, and the domination number of c801d93abe2" title="Click to view the MathML source">T_n$T_n$. Denoting the number of degree-k$k$ vertices in c801d93abe2" title="Click to view the MathML source">T_n$T_n$ by D_k$D_k$, we find that 33c03b6d6a79391b96322504" title="Click to view the MathML source">(D₁,…,D_m)$(D_1,\dots ,D_m)$ converges to a normal distribution for any fixed m$m$ as n→∞$n\to \infty$. The vertex domination number of c801d93abe2" title="Click to view the MathML source">T_n$T_n$ is also asymptotically normally distributed as n→∞$n\to \infty$. The diameter of c801d93abe2" title="Click to view the MathML source">T_n$T_n$ shifted by −2$-2$ is binomially distributed with parameters n−3$n-3$ and 1/2$1/2$. Finally, we find the asymptotic distribution of the maximum degree in c801d93abe2" title="Click to view the MathML source">T_n$T_n$, which is concentrated around log₂n${log}_{2}n$.