Brignall, Robert; Ruškuc, Nik and Vatter, Vincent
(2011).
This is the latest version of this eprint. 

PDF (Accepted Manuscript)
 Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (208Kb) 
DOI (Digital Object Identifier) Link:  https://doi.org/10.1112/S0025579310001518 

Google Scholar:  Look up in Google Scholar 
Abstract
An interval in a combinatorial structure R is a set I of points which are related to every point in R\I in the same way. A structure is simple if it has no proper intervals. Every combinatorial structure can be expressed as an inflation of a simple structure by structures of smaller sizes — this is called the substitution (or modular) decomposition. In this paper we prove several results of the following type: An arbitrary structure S of size n belonging to a class C can be embedded into a simple structure from C by adding at most f(n) elements. We prove such results when C is the class of all tournaments, graphs, permutations, posets, digraphs, oriented graphs and general relational structures containing a relation of arity greater than 2. The function f(n) in these cases is 2, ⌈log_{2}(n + 1)⌉, ⌈(n + 1)/2⌉, ⌈(n + 1)/2⌉, ⌈log_{4}(n + 1)⌉, ⌈log_{3}(n + 1)⌉ and 1, respectively. In each case these bounds are best possible.
Item Type:  Journal Article 

Copyright Holders:  2010 University College London 
ISSN:  20417942 
Keywords:  indecomposable graph; modular decomposition; prime graph; simple permutation; simple poset; simple tournament; substitution decomposition 
Academic Unit/School:  Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics Faculty of Science, Technology, Engineering and Mathematics (STEM) 
Item ID:  29672 
Depositing User:  Robert Brignall 
Date Deposited:  06 Oct 2011 08:38 
Last Modified:  29 Nov 2016 17:38 
URI:  http://oro.open.ac.uk/id/eprint/29672 
Share this page: 
Available Versions of this Item

Simple extensions of combinatorial structures. (deposited 12 Sep 2011 09:54)
 Simple extensions of combinatorial structures. (deposited 06 Oct 2011 08:38) [Currently Displayed]
Altmetrics  Scopus Citations 
Download history for this item
These details should be considered as only a guide to the number of downloads performed manually. Algorithmic methods have been applied in an attempt to remove automated downloads from the displayed statistics but no guarantee can be made as to the accuracy of the figures.