Bohman, Tom, Fonoberova, Maria and Pikhurko, Oleg. (2011) The saturation function of complete partite graphs. Journal of Combinatorics, Vol.1 (No.2). pp. 149-170. ISSN 1942-5600

Full text not available from this repository.

Abstract

A graph G is called F-saturated if it is F-free but the addition of any missing edge to G creates a copy of F. Let the saturation function sat(n, F) be the minimum number of edges that an F-saturated graph on n vertices can have. We determine this function asymptotically for every fixed complete partite graph F as n tends to infinity and give some structural information about almost extremal F-saturated graphs. If the two largest parts of F have different sizes, then we can reduce the error term to an additive constant.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Mathematics
Journal or Publication Title:	Journal of Combinatorics
Publisher:	International Press
ISSN:	1942-5600
Official Date:	2011
Volume:	Vol.1
Number:	No.2
Page Range:	pp. 149-170
Identification Number:	10.1137/090751530
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
URI:	http://wrap.warwick.ac.uk/id/eprint/43796

Request changes or add full text files to a record

Actions (login required)

View Item