کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646765 1342313 2016 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On random trees obtained from permutation graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On random trees obtained from permutation graphs
چکیده انگلیسی

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 nn vertices is 2n−22n−2 for n≥2n≥2. We then study TnTn, a uniformly random tree from this set of trees. In particular, we study the number of vertices of a given degree in TnTn, the maximum degree in TnTn, the diameter of TnTn, and the domination number of TnTn. Denoting the number of degree-kk vertices in TnTn by DkDk, we find that (D1,…,Dm)(D1,…,Dm) converges to a normal distribution for any fixed mm as n→∞n→∞. The vertex domination number of TnTn is also asymptotically normally distributed as n→∞n→∞. The diameter of TnTn shifted by −2−2 is binomially distributed with parameters n−3n−3 and 1/21/2. Finally, we find the asymptotic distribution of the maximum degree in TnTn, which is concentrated around log2nlog2n.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 12, 6 December 2016, Pages 2871–2883
نویسندگان
, ,