Bichain graphs: Geometric model and universal graphs

被引：1

作者：

Brignall, Robert ^{[1
]}

Lozin, Vadim V. ^{[2
,3
]}

Stacho, Juraj ^{[2
,3
]}

机构：

[1] Open Univ, Dept Math & Stat, Milton Keynes MK7 6AA, Bucks, England

[2] Univ Warwick, DIMAP, Coventry CV4 7AL, W Midlands, England

[3] Univ Warwick, Math Inst, Coventry CV4 7AL, W Midlands, England

来源：

DISCRETE APPLIED MATHEMATICS | 2016年 / 199卷

基金：

英国工程与自然科学研究理事会;

关键词：

Intersection graph; Universal graph; Split permutation graph; CLIQUE-WIDTH; SPLIT GRAPHS;

D O I：

10.1016/j.dam.2014.08.031

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 n(2) vertices. The latter result improves a recent cubic construction of universal split permutation graphs. (C) 2014 Elsevier B.V. All rights reserved.

引用

页码：16 / 29

页数：14

共 17 条

[1] UNIVERSAL GRAPHS AND UNIVERSAL PERMUTATIONS [J].

Atminas, Aistis ;

Lozin, Vadim V. ;

Kitaev, Sergey ;

Valyuzhenich, Alexandr .

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2013, 5 (04)

[2] The speed of hereditary properties of graphs [J].

Balogh, J ;

Bollobás, B ;

Weinreich, D .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2000, 79 (02) :131-156

[3] SPLIT GRAPHS OF DILWORTH NUMBER-2 [J].

BENZAKEN, C ;

HAMMER, PL ;

DEWERRA, D .

DISCRETE MATHEMATICS, 1985, 55 (02) :123-127

[4] Clique-width for 4-vertex forbidden subgraphs [J].

Brandstaedt, Andreas ;

Engelfriet, Joost ;

Le, Hoang-Oanh ;

Lozin, Vadim V. .

THEORY OF COMPUTING SYSTEMS, 2006, 39 (04) :561-590

[5]

Cormen T. H., 2009, Introduction to Algorithms

[6] INDEPENDENCE AND DOMINATION IN POLYGON GRAPHS [J].

ELMALLAH, ES ;

STEWART, LK .

DISCRETE APPLIED MATHEMATICS, 1993, 44 (1-3) :65-77

[7]

FROST HB, 1990, ARS COMBINATORIA, V29, P283

[8] DIFFERENCE GRAPHS [J].

HAMMER, PL ;

PELED, UN ;

SUN, X .

DISCRETE APPLIED MATHEMATICS, 1990, 28 (01) :35-44

[9]

Hammer PL., 1994, COMB PROBAB COMPUT, V3, P327

[10] Bandwidth of chain graphs [J].

Kloks, T ;

Kratsch, D ;

Müller, H .

INFORMATION PROCESSING LETTERS, 1998, 68 (06) :313-315

← 1 2 →