The saturation function of complete partite graphs
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-5600Full text not available from this repository.
Official URL: http://dx.doi.org/10.1137/090751530
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 ﬁxed complete partite graph F as n tends to inﬁnity and give some structural information about almost extremal F-saturated graphs. If the two largest parts of F have diﬀerent 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|
|Page Range:||pp. 149-170|
|Access rights to Published version:||Restricted or Subscription Access|
Actions (login required)
Downloads per month over past year