The depression of a graph and k-kernels
Christina M. Mynhardt, Mark Schurch · Discussiones Mathematicae Graph Theory · 2013
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.