- Tytuł:
- The Saturation Number for the Length of Degree Monotone Paths
- Autorzy:
-
Caro, Yair
Lauri, Josef
Zarb, Christina - Powiązania:
- https://bibliotekanauki.pl/articles/31339330.pdf
- Data publikacji:
- 2015-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
paths
degrees
saturation - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2015, 35, 3; 557-569
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł