# Weak Saturation Numbers for Sparse Graphs

Ralph J. Faudree; Ronald J. Gould; Michael S. Jacobson

Discussiones Mathematicae Graph Theory (2013)

- Volume: 33, Issue: 4, page 677-693
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topRalph J. Faudree, Ronald J. Gould, and Michael S. Jacobson. "Weak Saturation Numbers for Sparse Graphs." Discussiones Mathematicae Graph Theory 33.4 (2013): 677-693. <http://eudml.org/doc/267922>.

@article{RalphJ2013,

abstract = {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.},

author = {Ralph J. Faudree, Ronald J. Gould, Michael S. Jacobson},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {saturated graphs; sparse graphs; weak saturation},

language = {eng},

number = {4},

pages = {677-693},

title = {Weak Saturation Numbers for Sparse Graphs},

url = {http://eudml.org/doc/267922},

volume = {33},

year = {2013},

}

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

VL - 33

IS - 4

SP - 677

EP - 693

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

LA - eng

KW - saturated graphs; sparse graphs; weak saturation

UR - http://eudml.org/doc/267922

ER -

## References

top- [1] M. Borowiecki and E. Sidorowicz, Weakly P-saturated graphs, Discuss. Math. Graph Theory 22 (2002) 17-22. doi:10.7151/dmgt.1155 [Crossref] Zbl1016.05044
- [2] B. Bollobás, Weakly k-saturated graphs, Beitr¨age ur Graphentheorie, Kolloquium, Manebach, 1967 (Teubner, Leipig, 1968) 25-31.
- [3] G. Chartrand and L. Lesniak, Graphs and Digraphs (Chapman and Hall, London, 2005). Zbl1057.05001
- [4] P. Erdös, Z. Füredi and Zs. Tuza, Saturated r-uniform hyperegraphs, Discrete Math. 98 (1991) 95-104. doi:10.1016/0012-365X(91)90035-Z[Crossref]
- [5] P. Erdös, A. Hajnal and J.W. Moon, A problem in graph theory, Amer. Math. Monthly 71 (1964) 1107-1110. doi:10.2307/2311408[Crossref]
- [6] J.R. Faudree, R.J. Faudree and J. Schmitt, A survey of minimum saturated graphs Electron. J. Combin. DS19 (2011) 36 pages. Zbl1222.05113
- [7] J.R. Faudree, R.J. Faudree, R.J. Gould and M.S. Jacobson, Saturation numbers for trees, Electron. J. Combin. 16 (2009). Zbl1186.05072
- [8] 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[Crossref]
- [9] L. Lovász, Flats in matroids and geometric graphs, Combinatorial Surveys (Proc. Sixth British Combinatorial Conf.), Royal Holloway Coll., Egham (Academic Press, London, 1977) 45-86.
- [10] O. Pikhurko, Weakly saturated hypergraphs and exterior algebra, Combin. Probab.Comput. 10 (2001) 435-451. doi:10.1017/S0963548301004746[Crossref] Zbl1002.05053
- [11] E. Sidorowicz, Size of weakly saturated graphs, Discrete Math. 307 (2007) 1486-1492. doi:10.1016/j.disc.2005.11.085[Crossref][WoS] Zbl1118.05046
- [12] L. Taylor Ollmann, K2,2 saturated graphs with a minimal number of edges, in: Proceedings of the Third Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla.) (1972), 367-392.
- [13] Zs. Tuza, Extremal Problems on saturated graphs and hypergraphs, Ars Combin. 25B (1988) Eleventh British Combinatorial Conference (London (1987)), 105-113.
- [14] Zs. Tuza, Asymptotic growth of sparse saturated structures is locally determined, Discrete Math. 108 (1992) 397-402. doi:10.1016/0012-365X(92)90692-9 [Crossref]