# The Saturation Number for the Length of Degree Monotone Paths

Yair Caro; Josef Lauri; Christina Zarb

Discussiones Mathematicae Graph Theory (2015)

- Volume: 35, Issue: 3, page 557-569
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topYair Caro, Josef Lauri, and Christina Zarb. "The Saturation Number for the Length of Degree Monotone Paths." Discussiones Mathematicae Graph Theory 35.3 (2015): 557-569. <http://eudml.org/doc/271208>.

@article{YairCaro2015,

abstract = {A degree monotone path in a graph G is a path P such that the sequence of degrees of the vertices in the order in which they appear on P is monotonic. The length (number of vertices) of the longest degree monotone path in G is denoted by mp(G). This parameter, inspired by the well-known Erdős- Szekeres theorem, has been studied by the authors in two earlier papers. Here we consider a saturation problem for the parameter mp(G). We call G saturated if, for every edge e added to G, mp(G + e) > mp(G), and we define h(n, k) to be the least possible number of edges in a saturated graph G on n vertices with mp(G) < k, while mp(G+e) ≥ k for every new edge e. We obtain linear lower and upper bounds for h(n, k), we determine exactly the values of h(n, k) for k = 3 and 4, and we present constructions of saturated graphs.},

author = {Yair Caro, Josef Lauri, Christina Zarb},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {paths; degrees; saturation.; saturation},

language = {eng},

number = {3},

pages = {557-569},

title = {The Saturation Number for the Length of Degree Monotone Paths},

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

volume = {35},

year = {2015},

}

TY - JOUR

AU - Yair Caro

AU - Josef Lauri

AU - Christina Zarb

TI - The Saturation Number for the Length of Degree Monotone Paths

JO - Discussiones Mathematicae Graph Theory

PY - 2015

VL - 35

IS - 3

SP - 557

EP - 569

AB - A degree monotone path in a graph G is a path P such that the sequence of degrees of the vertices in the order in which they appear on P is monotonic. The length (number of vertices) of the longest degree monotone path in G is denoted by mp(G). This parameter, inspired by the well-known Erdős- Szekeres theorem, has been studied by the authors in two earlier papers. Here we consider a saturation problem for the parameter mp(G). We call G saturated if, for every edge e added to G, mp(G + e) > mp(G), and we define h(n, k) to be the least possible number of edges in a saturated graph G on n vertices with mp(G) < k, while mp(G+e) ≥ k for every new edge e. We obtain linear lower and upper bounds for h(n, k), we determine exactly the values of h(n, k) for k = 3 and 4, and we present constructions of saturated graphs.

LA - eng

KW - paths; degrees; saturation.; saturation

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

ER -

## References

top- [1] B. Bollobás, Extremal Graph Theory (Dover Publications, New York, 2004). Zbl1099.05044
- [2] Y. Caro, J. Lauri and C. Zarb, Degree monotone paths, ArXiv e-prints (2014) submitted. Zbl1317.05030
- [3] Y. Caro, J. Lauri and C. Zarb, Degree monotone paths and graph operations, ArXiv e-prints (2014) submitted.
- [4] J. Deering, Uphill and downhill domination in graphs and related graph parameters, Ph.D. Thesis, ETSU (2013).
- [5] J. Deering, T.W. Haynes, S.T. Hedetniemi and W. Jamieson, Downhill and uphill domination in graphs, (2013) submitted.
- [6] J. Deering, T.W. Haynes, S.T. Hedetniemi and W. Jamieson, A Polynomial time algorithm for downhill and uphill domination, (2013) submitted.
- [7] M. Eliáš and J. Matoušek, Higher-order Erdős-Szekeres theorems, Adv. Math. 244 (2013) 1-15. doi:10.1016/j.aim.2013.04.020[Crossref] Zbl1283.05175
- [8] 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]
- [9] P. Erdős and G. Szekeres, A combinatorial problem in geometry, Compos. Math. 2 (1935) 463-470. Zbl0012.27010
- [10] J.R. Faudree, R.J. Faudree and J.R. Schmitt, A survey of minimum saturated graphs, Electron. J. Combin. 18 (2011) #DS19. Zbl1222.05113
- [11] T.W. Haynes, S.T. Hedetniemi, J.D. Jamieson and W.B. Jamieson, Downhill dom- ination in graphs, Discuss. Math. Graph Theory 34 (2014) 603-612. doi:10.7151/dmgt.1760[Crossref] Zbl1295.05176
- [12] 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] Zbl0593.05041

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.