The Open UniversitySkip to content
 

Bichain graphs: geometric model and universal graphs

Brignall, Robert; Lozin, Vadim V. and Stacho, Juraj (2016). Bichain graphs: geometric model and universal graphs. Discrete Applied Mathematics, 199 pp. 16–29.

DOI (Digital Object Identifier) Link: https://doi.org/10.1016/j.dam.2014.08.031
Google Scholar: Look up in Google Scholar

Abstract

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 n-universal bichain graph with n2 vertices. The latter result improves a recent cubic construction of universal split permutation graphs.

Item Type: Journal Item
Copyright Holders: 2014 Elsevier B.V
ISSN: 0166-218X
Project Funding Details:
Funded Project NameProject IDFunding Body
Infinite Antichains of Combinatorial StructuresEP/J006130/1EPSRC (Engineering and Physical Sciences Research Council)
Keywords: intersection graph; universal graph; split permutation graph
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 40985
Depositing User: Robert Brignall
Date Deposited: 30 Sep 2014 09:37
Last Modified: 07 Dec 2018 10:25
URI: http://oro.open.ac.uk/id/eprint/40985
Share this page:

Metrics

Altmetrics from Altmetric

Citations from Dimensions

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU