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

Abstract

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

How to cite

top

Yair 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. [1] B. Bollobás, Extremal Graph Theory (Dover Publications, New York, 2004). Zbl1099.05044
  2. [2] Y. Caro, J. Lauri and C. Zarb, Degree monotone paths, ArXiv e-prints (2014) submitted. Zbl1317.05030
  3. [3] Y. Caro, J. Lauri and C. Zarb, Degree monotone paths and graph operations, ArXiv e-prints (2014) submitted. 
  4. [4] J. Deering, Uphill and downhill domination in graphs and related graph parameters, Ph.D. Thesis, ETSU (2013). 
  5. [5] J. Deering, T.W. Haynes, S.T. Hedetniemi and W. Jamieson, Downhill and uphill domination in graphs, (2013) submitted. 
  6. [6] J. Deering, T.W. Haynes, S.T. Hedetniemi and W. Jamieson, A Polynomial time algorithm for downhill and uphill domination, (2013) submitted. 
  7. [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. [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. [9] P. Erdős and G. Szekeres, A combinatorial problem in geometry, Compos. Math. 2 (1935) 463-470. Zbl0012.27010
  10. [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. [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. [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 ?

top

You must be logged in to post comments.