Saturation Spectrum of Paths and Stars

Faudree, Jill; Faudree, Ralph J.; Gould, Ronald J.; Jacobson, Michael S.; Thomas, Brent J.

Geodesic

Parcourir par

Saturation Spectrum of Paths and Stars

Faudree, Jill ; Faudree, Ralph J. ; Gould, Ronald J. ; Jacobson, Michael S. ; Thomas, Brent J.

Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 811-822

Voir la notice de l'article provenant de la source Library of Science

Résumé

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, P_k) to within a constant of ex(n, P_k) when n is sufficiently large.

Keywords: saturation spectrum, stars, paths

@article{DMGT_2017_37_3_a21,
     author = {Faudree, Jill and Faudree, Ralph J. and Gould, Ronald J. and Jacobson, Michael S. and Thomas, Brent J.},
     title = {Saturation {Spectrum} of {Paths} and {Stars}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {811--822},
     publisher = {mathdoc},
     volume = {37},
     number = {3},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a21/}
}

TY  - JOUR
AU  - Faudree, Jill
AU  - Faudree, Ralph J.
AU  - Gould, Ronald J.
AU  - Jacobson, Michael S.
AU  - Thomas, Brent J.
TI  - Saturation Spectrum of Paths and Stars
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 811
EP  - 822
VL  - 37
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a21/
LA  - en
ID  - DMGT_2017_37_3_a21
ER  -

%0 Journal Article
%A Faudree, Jill
%A Faudree, Ralph J.
%A Gould, Ronald J.
%A Jacobson, Michael S.
%A Thomas, Brent J.
%T Saturation Spectrum of Paths and Stars
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 811-822
%V 37
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a21/
%G en
%F DMGT_2017_37_3_a21

Faudree, Jill; Faudree, Ralph J.; Gould, Ronald J.; Jacobson, Michael S.; Thomas, Brent J. Saturation Spectrum of Paths and Stars. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 811-822. http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a21/