A study on random permutation graphs

Authors Oğuz Gürerk, Ümit Işlak, M. Yildiz

Publication date 20 January 2019

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Abstract: For a given permutation

p i_{n}

in

S_{n}

, a random permutation graph is formed by including an edge between two vertices

i

and

j

if and only if

(i - j) (p i_{n} (i) - p i_{n} (j)) < 0

. In this paper, we study various statistics of random permutation graphs. In particular, the degree of a given node, the number of nodes with a given degree, the number of isolated vertices, and the number of cliques are analyzed. Further, explicit formulas for the probabilities of having a given number of connected components and isolated vertices are obtained.

This page was built for publication: A study on random permutation graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6312740)