The Saturation Number for the Length of Degree Monotone Paths
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- Szeke...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2015-08-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1817 |
| _version_ | 1827832773531926528 |
|---|---|
| author | Caro Yair Lauri Josef Zarb Christina |
| author_facet | Caro Yair Lauri Josef Zarb Christina |
| author_sort | Caro Yair |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T05:19:26Z |
| format | Article |
| id | doaj.art-238bd63ac8e84aaaa5523b15ca954c86 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T05:19:26Z |
| publishDate | 2015-08-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-238bd63ac8e84aaaa5523b15ca954c862023-09-03T07:47:24ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922015-08-0135355756910.7151/dmgt.1817dmgt.1817The Saturation Number for the Length of Degree Monotone PathsCaro Yair0Lauri Josef1Zarb Christina2Department of Mathematics University of Haifa-Oranim, IsraelDepartment of Mathematics University of Malta, MaltaDepartment of Mathematics University of Malta, MaltaA 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.https://doi.org/10.7151/dmgt.1817pathsdegreessaturation. |
| spellingShingle | Caro Yair Lauri Josef Zarb Christina The Saturation Number for the Length of Degree Monotone Paths Discussiones Mathematicae Graph Theory paths degrees saturation. |
| title | The Saturation Number for the Length of Degree Monotone Paths |
| title_full | The Saturation Number for the Length of Degree Monotone Paths |
| title_fullStr | The Saturation Number for the Length of Degree Monotone Paths |
| title_full_unstemmed | The Saturation Number for the Length of Degree Monotone Paths |
| title_short | The Saturation Number for the Length of Degree Monotone Paths |
| title_sort | saturation number for the length of degree monotone paths |
| topic | paths degrees saturation. |
| url | https://doi.org/10.7151/dmgt.1817 |
| work_keys_str_mv | AT caroyair thesaturationnumberforthelengthofdegreemonotonepaths AT laurijosef thesaturationnumberforthelengthofdegreemonotonepaths AT zarbchristina thesaturationnumberforthelengthofdegreemonotonepaths AT caroyair saturationnumberforthelengthofdegreemonotonepaths AT laurijosef saturationnumberforthelengthofdegreemonotonepaths AT zarbchristina saturationnumberforthelengthofdegreemonotonepaths |