Geodesic
Saturation Spectrum of Paths and Stars
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

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.
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/

[1] K. Amin, J. Faudree and R.J. Gould, The edge spectrum of K4 -saturated graphs, J. Combin. Math. Combin. Comput. 81 (2012) 233–242.

[2] K. Amin, J. Faudree, R.J. Gould and E. Sidorowicz, On the non-(p−1)-partite Kp-free graphs, Discuss. Math. Graph Theory 33 (2013) 9–23. doi:10.7151/dmgt.1654

[3] C. Barefoot, K. Casey, D. Fisher, K. Fraughnaugh and F. Harary, Size in maximal triangle-free graphs and minimal graphs of diameter 2, Discrete Math. 138 (1995) 93–99. doi:10.1016/0012-365X(94)00190-T

[4] G. Chartrand, L. Lesniak and P. Zhang, Graphs & Digraphs (CRC Press, 2010).

[5] P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959) 337–356.

[6] R.J. Gould, W. Tang, E. Wei and C.-Q. Zhang, The edge spectrum of the saturation number for small paths, Discrete Math. 312 (2012) 2682–2689. doi:10.1016/j.disc.2012.01.012

[7] L. Kászonyi and Zs. Tuza, Saturated graphs with minimal number of edges, J. Graph Theory 10 (1986) 203–210. doi:10.1002/jgt.3190100209