- Tytuł:
- The depression of a graph and k-kernels
- Autorzy:
-
Schurch, Mark
Mynhardt, Christine - Powiązania:
- https://bibliotekanauki.pl/articles/30148230.pdf
- Data publikacji:
- 2014-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
edge ordering of a graph
increasing path
monotone path
depression - Opis:
- An edge ordering of a graph G is an injection f : E(G) → R, the set of real numbers. A path in G for which the edge ordering f increases along its edge sequence is called an f-ascent ; an f-ascent is maximal if it is not contained in a longer f-ascent. The depression of G is the smallest integer k such that any edge ordering f has a maximal f-ascent of length at most k. A k-kernel of a graph G is a set of vertices U ⊆ V (G) such that for any edge ordering f of G there exists a maximal f-ascent of length at most k which neither starts nor ends in U. Identifying a k-kernel of a graph G enables one to construct an infinite family of graphs from G which have depression at most k. We discuss various results related to the concept of k-kernels, including an improved upper bound for the depression of trees.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2014, 34, 2; 233-247
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki