Atminas, Aistis and Kitaev, Sergey and Lozin, Vadim and Valyuzhenich, Alexander (2013) Universal graphs and universal permutations. Discrete Mathematics, Algorithms and Applications, 5 (4). ISSN 1793-8317Full text not available in this repository. (Request a copy from the Strathclyde author)
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.
|Keywords:||universal graphs, bipartite permutation graphs, split permutation graphs, 321-avoiding permutations, Mathematics|
|Subjects:||Science > Mathematics|
|Department:||Faculty of Science > Computer and Information Sciences|
|Depositing user:||Pure Administrator|
|Date Deposited:||21 Oct 2014 10:30|
|Last modified:||22 Mar 2017 13:35|