Weak Saturation Numbers for Sparse Graphs
Discussiones Mathematicae Graph Theory, Tome 33 (2013) no. 4, p. 677.
Voir la notice de l'article dans European Digital Mathematics Library
For a fixed graph F, a graph G is F-saturated if there is no copy of F in G, but for any edge e ∉ G, there is a copy of F in G + e. The minimum number of edges in an F-saturated graph of order n will be denoted by sat(n, F). A graph G is weakly F-saturated if there is an ordering of the missing edges of G so that if they are added one at a time, each edge added creates a new copy of F. The minimum size of a weakly F-saturated graph G of order n will be denoted by wsat(n, F). The graphs of order n that are weakly F-saturated will be denoted by wSAT(n, F), and those graphs in wSAT(n, F) with wsat(n, F) edges will be denoted by wSAT(n, F). The precise value of wsat(n, T) for many families of sparse graphs, and in particular for many trees, will be determined. More specifically, families of trees for which wsat(n, T) = |T|−2 will be determined. The maximum and minimum values of wsat(n, T) for the class of all trees will be given. Some properties of wsat(n, T) and wSAT(n, T) for trees will be discussed. Keywords: saturated graphs, sparse graphs, weak saturation.
@article{DMGT_2013__33_4_267922,
author = {Ralph J. Faudree and Ronald J. Gould and Michael S. Jacobson},
title = {Weak {Saturation} {Numbers} for {Sparse} {Graphs}},
journal = {Discussiones Mathematicae Graph Theory},
pages = {677},
publisher = {mathdoc},
volume = {33},
number = {4},
year = {2013},
zbl = {1295.05130},
language = {en},
url = {https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_4_267922/}
}
TY - JOUR AU - Ralph J. Faudree AU - Ronald J. Gould AU - Michael S. Jacobson TI - Weak Saturation Numbers for Sparse Graphs JO - Discussiones Mathematicae Graph Theory PY - 2013 SP - 677 VL - 33 IS - 4 PB - mathdoc UR - https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_4_267922/ LA - en ID - DMGT_2013__33_4_267922 ER -
%0 Journal Article %A Ralph J. Faudree %A Ronald J. Gould %A Michael S. Jacobson %T Weak Saturation Numbers for Sparse Graphs %J Discussiones Mathematicae Graph Theory %D 2013 %P 677 %V 33 %N 4 %I mathdoc %U https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_4_267922/ %G en %F DMGT_2013__33_4_267922
Ralph J. Faudree; Ronald J. Gould; Michael S. Jacobson. Weak Saturation Numbers for Sparse Graphs. Discussiones Mathematicae Graph Theory, Tome 33 (2013) no. 4, p. 677. https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_4_267922/