Universal graphs and universal permutations

DOI10.1142/S1793830913500389MaRDI QIDQ2874053zbMATH OpenOpenAlexFDO

Authors Aistis Atminas, Sergey Kitaev, Alexandr Valyuzhenich, Vadim Lozin

Publication date 28 January 2014

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.6192

zbMATH Keywords

321-avoiding permutationsbipartite permutation graphssplit permutation graphsuniversal graphs

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)

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_n$ as induced subgraphs is called $n$-universal for $X$. Moreover, we say that $U^{(n)}$ is a proper $n$-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$ vertices, which means that this construction is order-optimal.

Recommendations

• scientific article; zbMATH DE number 5720940
• Bichain graphs: geometric model and universal graphs
• Exoticn-universal graphs
• Small universal graphs
• Universal graphs and induced-universal graphs

Cites work

• Implicat Representation of Graphs
• Induced-universal graphs for graphs with bounded maximum degree
• Nonexistence of universal graphs without some trees
• On induced-universal graphs for the class of bounded-degree graphs
• On minimal n-universal graphs
• On Universal Threshold Graphs
• Patterns in permutations and words.
• Some universal graphs
• Split graphs of Dilworth number 2
• Universal graphs and induced-universal graphs
• Universal graphs without large bipartite subgraphs

Cited in

(5)

• Exoticn-universal graphs
• Some remarks on universal graphs
• Graph Traversals as Universal Constructions
• Induced subgraphs of zero-divisor graphs
• Bichain graphs: geometric model and universal graphs

This page was built for publication: Universal graphs and universal permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2874053)