Geodesic
The depression of a graph and k-kernels
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 2, pp. 233-247

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: edge ordering of a graph, increasing path, monotone path, depression 
@article{DMGT_2014_34_2_a2,
     author = {Schurch, Mark and Mynhardt, Christine},
     title = {The depression of a graph and \protect\emph{k}-kernels},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {233--247},
     publisher = {mathdoc},
     volume = {34},
     number = {2},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a2/}
}
TY  - JOUR
AU  - Schurch, Mark
AU  - Mynhardt, Christine
TI  - The depression of a graph and k-kernels
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 233
EP  - 247
VL  - 34
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a2/
LA  - en
ID  - DMGT_2014_34_2_a2
ER  - 
%0 Journal Article
%A Schurch, Mark
%A Mynhardt, Christine
%T The depression of a graph and k-kernels
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 233-247
%V 34
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a2/
%G en
%F DMGT_2014_34_2_a2
Schurch, Mark; Mynhardt, Christine. The depression of a graph and k-kernels. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 2, pp. 233-247. http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a2/