The Library
The saturation function of complete partite graphs
Tools
Tools
Tools
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.
Official URL: http://dx.doi.org/10.1137/090751530
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 |
| 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 |
Actions (login required)
 |
View Item |
