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">span>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">span>span>span> vertices. The latter result improves a recent cubic construction of universal split permutation graphs.
NGLC 2004-2010.National Geological Library of China All Rights Reserved.
Add:29 Xueyuan Rd,Haidian District,Beijing,PRC. Mail Add: 8324 mailbox 100083
For exchange or info please contact us via email.