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. doi:10.1137/090751530
Research output not available from this repository, contact author.
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 | ||||
| Official Date: | 2011 | ||||
| Dates: |
|
||||
| Volume: | Vol.1 | ||||
| Number: | No.2 | ||||
| Page Range: | pp. 149-170 | ||||
| DOI: | 10.1137/090751530 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
