Geodesic
Gaps in the Saturation Spectrum of Trees
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 157-170

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 the complement of G to G results in a copy of H. The minimum number of edges (the 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 show that paths, trees with a vertex adjacent to many leaves, and brooms have a gap in the saturation spectrum.
Keywords: saturation spectrum, tree, saturation number 
@article{DMGT_2019_39_1_a12,
     author = {Horn, Paul and Gould, Ronald J. and Jacobson, Michael S. and Thomas, Brent J.},
     title = {Gaps in the {Saturation} {Spectrum} of {Trees}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {157--170},
     publisher = {mathdoc},
     volume = {39},
     number = {1},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a12/}
}
TY  - JOUR
AU  - Horn, Paul
AU  - Gould, Ronald J.
AU  - Jacobson, Michael S.
AU  - Thomas, Brent J.
TI  - Gaps in the Saturation Spectrum of Trees
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 157
EP  - 170
VL  - 39
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a12/
LA  - en
ID  - DMGT_2019_39_1_a12
ER  - 
%0 Journal Article
%A Horn, Paul
%A Gould, Ronald J.
%A Jacobson, Michael S.
%A Thomas, Brent J.
%T Gaps in the Saturation Spectrum of Trees
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 157-170
%V 39
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a12/
%G en
%F DMGT_2019_39_1_a12
Horn, Paul; Gould, Ronald J.; Jacobson, Michael S.; Thomas, Brent J. Gaps in the Saturation Spectrum of Trees. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 157-170. http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a12/