Universal graphs and universal permutations

Aistis Atminas; Vadim V. Lozin; Sergey Kitaev; Alexandr Valyuzhenich

doi:10.1142/S1793830913500389

Universal graphs and universal permutations

Aistis Atminas, Vadim V. Lozin, Sergey Kitaev, Alexandr Valyuzhenich

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

Abstract

Let X be a family of graphs and X_n the set of n-vertex graphs in X. A graph U⁽ⁿ⁾ containing all graphs from X_nn as induced subgraphs is called n-universal for X. Moreover, we say that U⁽ⁿ⁾⁽ⁿ⁾ 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³⁽ⁿ⁾ 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	https://doi.org/10.1142/S1793830913500389
Publication status	Published - 1 Dec 2013
Externally published	Yes

Keywords

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

Access to Document

10.1142/S1793830913500389

Cite this

Atminas, A., Lozin, V. V., Kitaev, S., & Valyuzhenich, A. (2013). Universal graphs and universal permutations. Discrete Mathematics, Algorithms and Applications, 5(4), Article 1350038. https://doi.org/10.1142/S1793830913500389

@article{2a8fab928db84c4b907fef76aebc83d4,

title = "Universal graphs and universal permutations",

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 Xnn 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 4n3(n) vertices, which means that this construction is order-optimal.",

keywords = "321-avoiding permutations, Bipartite permutation graphs, Split permutation graphs, Universal graphs",

author = "Aistis Atminas and Lozin, {Vadim V.} and Sergey Kitaev and Alexandr Valyuzhenich",

note = "Publisher Copyright: {\textcopyright} 2013 World Scientific Publishing Company.",

year = "2013",

month = dec,

day = "1",

doi = "10.1142/S1793830913500389",

language = "English",

volume = "5",

journal = "Discrete Mathematics, Algorithms and Applications",

issn = "1793-8309",

number = "4",

}

TY - JOUR

T1 - Universal graphs and universal permutations

AU - Atminas, Aistis

AU - Lozin, Vadim V.

AU - Kitaev, Sergey

AU - Valyuzhenich, Alexandr

PY - 2013/12/1

Y1 - 2013/12/1

N2 - 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 Xnn 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 4n3(n) vertices, which means that this construction is order-optimal.

AB - 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 Xnn 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 4n3(n) vertices, which means that this construction is order-optimal.

KW - 321-avoiding permutations

KW - Bipartite permutation graphs

KW - Split permutation graphs

KW - Universal graphs

UR - http://www.scopus.com/inward/record.url?scp=84963591929&partnerID=8YFLogxK

U2 - 10.1142/S1793830913500389

DO - 10.1142/S1793830913500389

M3 - Article

AN - SCOPUS:84963591929

SN - 1793-8309

VL - 5

JO - Discrete Mathematics, Algorithms and Applications

JF - Discrete Mathematics, Algorithms and Applications

IS - 4

M1 - 1350038

ER -

Universal graphs and universal permutations

Abstract

Keywords

Access to Document

Other files and links

Cite this