## Abstract

Let X be a family of graphs and X_{n} the set of n-vertex graphs in X. A graph U^{(n)} containing all graphs from X_{nn} 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 4n^{3}^{(n)} vertices, which means that this construction is order-optimal.

Original language | English |
---|---|

Article number | 1350038 |

Journal | Discrete Mathematics, Algorithms and Applications |

Volume | 5 |

Issue number | 4 |

DOIs | |

Publication status | Published - 1 Dec 2013 |

Externally published | Yes |

## Keywords

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