Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: saturation.

Sortuj według:

Ogranicz wyniki do:

The Saturation Number for the Length of Degree Monotone Paths

100%

Caro Y., Lauri J., Zarb C.

Discussiones Mathematicae Graph Theory

2015

tom 35

nr 3

557-569

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Caro Y.

1 Lauri J.

1 Zarb C.

1 2015

Wyniki wyszukiwania

The Saturation Number for the Length of Degree Monotone Paths