Dabrowski, Konrad, Lozin, Vadim V. and Zamaraev, Victor. (2012) On factorial properties of chordal bipartite graphs. Discrete Mathematics, Vol.312 (No.16). pp. 2457-2465. ISSN 0012-365X

Full text not available from this repository.

Abstract

For a graph property X, let Xn 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 nc1n≤Xn≤nc2n for some positive constants c1 and c2. Hereditary properties with speed slower than factorial are surprisingly well structured. The situation with factorial properties is more complicated and less explored. To better understand the structure of factorial properties we look for minimal superfactorial ones. In [J.P. Spinrad, Nonredundant 1’s in Γ-free matrices, SIAM J. Discrete Math. 8 (1995) 251–257], Spinrad showed that the number of n-vertex chordal bipartite graphs is 2Θ(nlog2n), which means that this class is superfactorial. On the other hand, all subclasses of chordal bipartite graphs that have been studied in the literature, such as forest, bipartite permutation, bipartite distance-hereditary or convex graphs, are factorial. In this paper, we study more hereditary subclasses of chordal bipartite graphs and reveal both factorial and superfactorial members in this family. The latter fact shows that the class of chordal bipartite graphs is not a minimal superfactorial one. Finding minimal superfactorial classes in this family remains a challenging open question.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Mathematics
Journal or Publication Title:	Discrete Mathematics
Publisher:	Elsevier BV
ISSN:	0012-365X
Date:	August 2012
Volume:	Vol.312
Number:	No.16
Page Range:	pp. 2457-2465
Identification Number:	10.1016/j.disc.2012.04.010
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
URI:	http://wrap.warwick.ac.uk/id/eprint/48955

Request changes to a record

Actions (login required)

View Item