Saturation Spectrum of Paths and Stars

• Autorzy: Jill Faudree , Ralph J. Faudree , Ronald J. Gould , Michael S. Jacobson , Brent J. Thomas
• Języki publikacji: EN

Abstrakty

EN

A graph G is H-saturated if H is not a subgraph of G but the addition of any edge from G̅ to G results in a copy of H. The minimum size of an H-saturated graph on n vertices is denoted sat(n,H), while the maximum size is the well studied extremal number, ex(n,H). The saturation spectrum for a graph H is the set of sizes of H saturated graphs between sat(n,H) and ex(n,H). In this paper we completely determine the saturation spectrum of stars and we show the saturation spectrum of paths is continuous from sat(n, Pk) to within a constant of ex(n, Pk) when n is sufficiently large.

Słowa kluczowe

EN

saturation spectrum; stars; paths

Kategorie tematyczne

• 05C05: Trees
• 05C35: Extremal problems

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 3
• Strony: 811-822

Daty

wydano

2017-08-01

otrzymano

2015-10-29

poprawiono

2016-07-20

zaakceptowano

2016-07-20

online

2017-07-06

Twórcy

autor

Jill Faudree

• ,

autor

Ralph J. Faudree

• ,

autor

Ronald J. Gould

• ,

autor

Michael S. Jacobson

• ,

autor

Brent J. Thomas

• ,

Identyfikatory

DOI

10.7151/dmgt.1954