Universal graphs and universal permutations

Aistis Atminas, Sergey Kitaev, Vadim Lozin, Alexander Valyuzhenich

Research output: Contribution to journalArticlepeer-review

1 Citation (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 Xn as induced subgraphs is called n-universal for X. Moreover, we say that U(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 vertices, which means that this construction is order-optimal.
Original languageEnglish
Number of pages15
JournalDiscrete Mathematics, Algorithms and Applications
Issue number4
Early online date5 Nov 2013
Publication statusPublished - Dec 2013


  • universal graphs
  • bipartite permutation graphs
  • split permutation graphs
  • 321-avoiding permutations


Dive into the research topics of 'Universal graphs and universal permutations'. Together they form a unique fingerprint.

Cite this