On random trees obtained from permutation graphs

DOI10.1016/j.disc.2016.05.028zbMath1343.05133arXiv1406.3958OpenAlexW2473159957MaRDI QIDQ738839

Hüseyin Acan, Pawel Hitczenko

Publication date: 16 August 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1406.3958

zbMATH Keywords

diameterdomination numbermaximum degreepermutation graphindecomposable permutationpermutation tree

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Permutations, words, matrices (05A05) Distance in graphs (05C12)

Related Items

The number of occurrences of patterns in a random tree or forest permutation

Uses Software

• OEIS

Cites Work

• On the connected components of a random permutation graph with a given number of edges
• On the number of indecomposable permutations with a given number of cycles
• Finitely forcible graphons and permutons
• Transitivity and connectivity of permutations
• An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne-Goodman-Hedetniemi algorithm
• A linear algorithm for the domination number of a tree
• The limit distribution of the length of the longest head-run
• Threshold graphs and related topics
• A more general central limit theorem for \(m\)-dependent random variables with unbounded \(m\)
• Connected permutation graphs
• Bounding the number of edges in permutation graphs
• On the maximum degree in a random tree
• The central limit theorem for dependent random variables
• On degrees in the hasse diagram of the strong Bruhat order
• Distinctness of compositions of an integer: A probabilistic analysis
• On the Multiplicity of Parts in a Random Composition of a Large Integer
• On the height of trees
• Permutation Graphs and Transitive Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item