The Library
A note on the speed of hereditary graph properties
Tools
Lozin, Vadim V., Mayhill, Colin and Zamaraev, Victor. (2011) A note on the speed of hereditary graph properties. The Electronic Journal of Combinatorics, Vol.18 (No.1). p. 157. ISSN 2150959X

PDF
WRAP_Lozin_v18i1p157.pdf  Published Version  Requires a PDF viewer. Download (207Kb) 
Official URL: http://www.combinatorics.org/ojs/index.php/eljc/ar...
Abstract
For a graph property X, let X(n) be the number of graphs with vertex set {1, ..., n} having property X, also known as the speed of X. A property X is called factorial if X is hereditary (i.e. closed under taking induced subgraphs) and n(c1n) <= X(n) <= n(c2n) for some positive constants c(1) and c(2). Hereditary properties with the speed slower than factorial are surprisingly well structured. The situation with factorial properties is more complicated and less explored, although this family includes many properties of theoretical or practical importance, such as planar graphs or graphs of bounded vertex degree. To simplify the study of factorial properties,we propose the following conjecture: the speed of a hereditary property X is factorial if and only if the fastest of the following three properties is factorial: bipartite graphs in X, cobipartite graphs in X and split graphs in X. In this note, we verify the conjecture for hereditary properties defined by forbidden induced subgraphs with at most 4 vertices.
Item Type:  Journal Article  

Subjects:  Q Science > QA Mathematics  
Divisions:  Faculty of Science > Mathematics  
Library of Congress Subject Headings (LCSH):  Graph theory  
Journal or Publication Title:  The Electronic Journal of Combinatorics  
Publisher:  Electronic Journal of Combinatorics  
ISSN:  2150959X  
Official Date:  August 2011  
Dates: 


Volume:  Vol.18  
Number:  No.1  
Number of Pages:  14  
Page Range:  p. 157  
Status:  Peer Reviewed  
Publication Status:  Published  
Funder:  University of Warwick. Centre for Discrete Mathematics and Its Applications, Rossiĭskiĭ fond fundamentalʹnykh issledovaniĭ [Russian Foundation for Basic Research] (RFBR), FAP  
Grant number:  110100107a (RFFI), 20101.3.1111017012 (FAP)  
References:  [1] V.E. Alekseev, Range of values of entropy of hereditary classes of graphs, Diskret. 

URI:  http://wrap.warwick.ac.uk/id/eprint/38522 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Actions (login required)
View Item 
Downloads
Downloads per month over past year