DC Field | Value | Language |
---|---|---|
dc.contributor.author | Ferrara, Michael | ko |
dc.contributor.author | Kim, Jaehoon | ko |
dc.contributor.author | Yeager, Elyse | ko |
dc.date.accessioned | 2019-07-18T05:34:24Z | - |
dc.date.available | 2019-07-18T05:34:24Z | - |
dc.date.created | 2019-07-17 | - |
dc.date.created | 2019-07-17 | - |
dc.date.created | 2019-07-17 | - |
dc.date.issued | 2014-05 | - |
dc.identifier.citation | DISCRETE MATHEMATICS, v.322, pp.26 - 30 | - |
dc.identifier.issn | 0012-365X | - |
dc.identifier.uri | http://hdl.handle.net/10203/263350 | - |
dc.description.abstract | Given a family of graphs F, a graph G is F-saturated if no element of F is a subgraph of G, but for any edge e in (G) over bar, some element of F is a subgraph of G + e. Let sat (n, F) denote the minimum number of edges in an F-saturated graph of order n, which we refer to as the saturation number or saturation function of F. If F = {F}, then we instead say that G is F-saturated and write sat(n, F). For graphs G, H-1, ... , H-k, we write that G -> (H-1, ... , H-k) if every k-coloring of E(G) contains a monochromatic copy of H-i in color i for some i. A graph G is (H-1, ... , H-k)-Ramsey-minimal if G -> (H-1, ... , H-k) but for any e is an element of G, (G - e) negated right arrow (H-1, ... , H-k). Let R-min (H-1, ... , H-k) denote the family of (H-1, ... , H-k)-Ramsey-minimal graphs. In this paper, motivated in part by a conjecture of Hanson and Toft (1987), we prove that sat(n, R-min(m(1)K(2), ... , m(k)K(2))) = 3(m(1) + ... + m(k) - k) for m(1), ... , m(k) >= 1 and n > 3(m(1) + ... + m(k) - k), and we also characterize the saturated graphs of minimum size. The proof of this result uses a new technique, iterated recoloring, which takes advantage of the structure of H-i-saturated graphs to determine the saturation number of R-min(H-1, ... , H-k). (C) 2014 Elsevier B.V. All rights reserved. | - |
dc.language | English | - |
dc.publisher | ELSEVIER SCIENCE BV | - |
dc.title | Ramsey-minimal saturation numbers for matchings | - |
dc.type | Article | - |
dc.identifier.wosid | 000332814900005 | - |
dc.identifier.scopusid | 2-s2.0-84892914162 | - |
dc.type.rims | ART | - |
dc.citation.volume | 322 | - |
dc.citation.beginningpage | 26 | - |
dc.citation.endingpage | 30 | - |
dc.citation.publicationname | DISCRETE MATHEMATICS | - |
dc.identifier.doi | 10.1016/j.disc.2013.12.024 | - |
dc.contributor.localauthor | Kim, Jaehoon | - |
dc.contributor.nonIdAuthor | Ferrara, Michael | - |
dc.contributor.nonIdAuthor | Yeager, Elyse | - |
dc.description.isOpenAccess | N | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | Saturated graph | - |
dc.subject.keywordAuthor | Ramsey-minimal graph | - |
dc.subject.keywordAuthor | Matching | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.