{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,31]],"date-time":"2024-01-31T00:14:08Z","timestamp":1706660048992},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p> Let X be a family of graphs and X<jats:sub>n<\/jats:sub> the set of n-vertex graphs in X. A graph U<jats:sup>(n)<\/jats:sup> containing all graphs from X<jats:sub>n<\/jats:sub> as induced subgraphs is called n-universal for X. Moreover, we say that U<jats:sup>(n)<\/jats:sup> 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<jats:sup>3<\/jats:sup> vertices, which means that this construction is order-optimal. <\/jats:p>","DOI":"10.1142\/s1793830913500389","type":"journal-article","created":{"date-parts":[[2013,9,4]],"date-time":"2013-09-04T01:03:51Z","timestamp":1378256631000},"page":"1350038","source":"Crossref","is-referenced-by-count":2,"title":["UNIVERSAL GRAPHS AND UNIVERSAL PERMUTATIONS"],"prefix":"10.1142","volume":"05","author":[{"given":"AISTIS","family":"ATMINAS","sequence":"first","affiliation":[{"name":"DIMAP and Mathematic Institute, University of Warwick, Coventry CV4 7AL, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"VADIM V.","family":"LOZIN","sequence":"additional","affiliation":[{"name":"DIMAP and Mathematic Institute, University of Warwick, Coventry CV4 7AL, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SERGEY","family":"KITAEV","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Sciences, University of Strathclyde, Glasgow G1 1XH, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALEXANDR","family":"VALYUZHENICH","sequence":"additional","affiliation":[{"name":"Novosibirsk State University, 2 Pirogova Street, 630090, Novosibirsk, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2013,12,3]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90040-8"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-009-0860-x"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190140408"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70731-3"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.04.020"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200905"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830000122X"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1137\/0405049"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17333-2"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02787220"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1112\/S002557930001250X"},{"key":"rf14","first-page":"345","volume":"84","author":"Lozin V. V.","journal-title":"Ars Combin."},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1017\/S2040618500035139"},{"key":"rf16","doi-asserted-by":"crossref","first-page":"331","DOI":"10.4064\/aa-9-4-331-340","volume":"9","author":"Rado R.","journal-title":"Acta Arith."}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830913500389","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T18:13:52Z","timestamp":1565115232000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830913500389"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12]]},"references-count":14,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2013,12,3]]},"published-print":{"date-parts":[[2013,12]]}},"alternative-id":["10.1142\/S1793830913500389"],"URL":"https:\/\/doi.org\/10.1142\/s1793830913500389","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12]]}}}