Bichain graphs: Geometric model and universal graphs

详细信息    查看全文

• 作者：Robert Brignall<sup>asup><sup> ; sup><sup>r.brignall@open.ac.uk" class="auth_mail" title="E-mail the corresponding authorsup> ; Vadim V. Lozin<sup>bsup><sup> ; sup><sup>V.Lozin@warwick.ac.uk" class="auth_mail" title="E-mail the corresponding authorsup><sup> ; sup><sup>v.lozin@warwick.ac.uk" class="auth_mail" title="E-mail the corresponding authorsup> ; Juraj Stacho<sup>bsup><sup> ; sup><sup>1sup><sup> ; sup><sup>stacho@cs.toronto.edu" class="auth_mail" title="E-mail the corresponding authorsup>
• 关键词：Intersection graph ; Universal graph ; Split permutation graph
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：30 January 2016
• 年：2016
• 卷：199
• 期：Complete
• 页码：16-29
• 全文大小：599 K

文摘

Bichain graphs form a bipartite analog of split permutation graphs, also known as split graphs of Dilworth number 2. Unlike graphs of Dilworth number 1 that enjoy many nice properties, split permutation graphs are substantially more complex. To better understand the global structure of split permutation graphs, in the present paper we study their bipartite analog. We show that bichain graphs admit a simple geometric representation and have a universal element of quadratic order, i.e. an <span id="mmlsi1069" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X14003837&_mathId=si1069.gif&_user=111111111&_pii=S0166218X14003837&_rdoc=1&_issn=0166218X&md5=45a91d949d2524806f3fbbcf32838c18" title="Click to view the MathML source">nspan><span class="mathContainer hidden"><span class="mathCode">scroll">nspan>span>span>-universal bichain graph with <span id="mmlsi11" class="mathmlsrc"><span class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X14003837&_mathId=si11.gif&_user=111111111&_pii=S0166218X14003837&_rdoc=1&_issn=0166218X&md5=1c80492a28a514289741b5ace10dc817" title="Click to view the MathML source">n<sup>2sup>span><span class="mathContainer hidden"><span class="mathCode">scroll">sup>n2sup>span>span>span> vertices. The latter result improves a recent cubic construction of universal split permutation graphs.