Universal graphs and universal permutations

Aistis Atminas, Sergey Kitaev, Vadim Lozin, Alexander Valyuzhenich

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

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
Volume5
Issue number4
Early online date5 Nov 2013
DOIs
Publication statusPublished - Dec 2013

    Fingerprint

Keywords

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

Cite this