Bounding the number of edges in permutation graphs
Summary: Given an integer \(s\geq 0\) and a permutation \(\pi \in S_n\), let \(\Gamma_{\pi,s}\) be the graph on \(n\) vertices \(1, \dots, n\) where two vertices \(i<j\) are adjacent if the permutation flips their order and there are at most \(s\) integers \(k\), \(i < k< j\), such that \(\pi=[\dots j \dots k \dots i\ldots]\). In this short paper we determine the maximum number of edges in \(\Gamma_{\pi,s}\) for all \(s\geq 1\) and characterize all permutations \(\pi\) which achieve this maximum. This answers an open question of Adin and Roichman, who studied the case \(s=0\). We also consider another (closely related) permutation graph, defined by Adin and Roichman, and obtain asymptotically tight bounds on the maximum number of edges in it.
- On permutation graphs
- scientific article; zbMATH DE number 6667019 (Why is no real title available?)
- scientific article; zbMATH DE number 5519216 (Why is no real title available?)
- On the connected components of a random permutation graph with a given number of edges
- scientific article; zbMATH DE number 403954 (Why is no real title available?)
- Permutation graphs and the weak Bruhat order
- Edge domination on bipartite permutation graphs and cotriangulated graphs
- Characterization and enumeration of 3-regular permutation graphs
- On random trees obtained from permutation graphs
This page was built for publication: Bounding the number of edges in permutation graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2500963)
