Universal graphs and universal permutations

Aistis Atminas, Vadim V. Lozin, Sergey Kitaev, Alexandr Valyuzhenich

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


Let X be a family of graphs and Xn the set of n-vertex graphs in X. A graph U(n) containing all graphs from Xnn as induced subgraphs is called n-universal for X. Moreover, we say that U(n)(n) is a propern-universal graph for X if it belongs to X. In the present paper, we construct a proper n-universal graph for the class of split permutation graphs. Our solution includes two ingredients: a proper universal 321-avoiding permutation and a bijection between 321-avoiding permutations and symmetric split permutation graphs. The n-universal split permutation graph constructed in this paper has 4n3(n) vertices, which means that this construction is order-optimal.

Original languageEnglish
Article number1350038
JournalDiscrete Mathematics, Algorithms and Applications
Issue number4
Publication statusPublished - 1 Dec 2013
Externally publishedYes


  • 321-avoiding permutations
  • Bipartite permutation graphs
  • Split permutation graphs
  • Universal graphs

Cite this