# The depression of a graph and k-kernels

Mark Schurch; Christine Mynhardt

Discussiones Mathematicae Graph Theory (2014)

- Volume: 34, Issue: 2, page 233-247
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMark Schurch, and Christine Mynhardt. "The depression of a graph and k-kernels." Discussiones Mathematicae Graph Theory 34.2 (2014): 233-247. <http://eudml.org/doc/267588>.

@article{MarkSchurch2014,

abstract = {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.},

author = {Mark Schurch, Christine Mynhardt},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {edge ordering of a graph; increasing path; monotone path; de- pression; depression},

language = {eng},

number = {2},

pages = {233-247},

title = {The depression of a graph and k-kernels},

url = {http://eudml.org/doc/267588},

volume = {34},

year = {2014},

}

TY - JOUR

AU - Mark Schurch

AU - Christine Mynhardt

TI - The depression of a graph and k-kernels

JO - Discussiones Mathematicae Graph Theory

PY - 2014

VL - 34

IS - 2

SP - 233

EP - 247

AB - 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.

LA - eng

KW - edge ordering of a graph; increasing path; monotone path; de- pression; depression

UR - http://eudml.org/doc/267588

ER -

## References

top- [1] A. Bialostocki and Y. Roditty, A monotone path in an edge-ordered graph, Int. J. Math. Math. Sci. 10 (1987) 315-320. doi:10.1155/S0161171287000383[Crossref] Zbl0633.05043
- [2] A.P. Burger, E.J. Cockayne and C.M. Mynhardt, Altitude of small complete and complete bipartite graphs, Australas. J. Combin. 31 (2005) 167-177. Zbl1080.05046
- [3] A.R. Calderbank and F.R.K. Chung and D.G. Sturtevant, Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs, Discrete Math. 50 (1984) 15-28. doi:10.1016/0012-365X(84)90031-1[Crossref] Zbl0542.05058
- [4] G. Chartrand and L.M. Lesniak, Graphs and Digraphs (Third Ed.) (Wadsworth, 1996).
- [5] V. Chv´atal and J. Koml´os, Some combinatorial theorems on monotonicity, Canad. Math. Bull. 14 (1971) 151-157. doi:10.4153/CMB-1971-028-8[Crossref]
- [6] T.C. Clark and B. Falvai, N.D.R. Henderson and C.M. Mynhardt, Altitude of 4- regular circulants, AKCE Int. J. Graphs Comb. 1 (2004) 149-166. Zbl1073.05061
- [7] E.J. Cockayne and G. Geldenhuys, P.J.P Grobler, C.M. Mynhardt and J.H. van Vuuren, The depression of a graph, Util. Math. 69 (2006) 143-160. Zbl1111.05086
- [8] E.J. Cockayne and C.M. Mynhardt, Altitude of K3,n, J. Combin. Math. Combin. Comput. 52 (2005) 143-157. Zbl1073.05062
- [9] E.J. Cockayne and C.M. Mynhardt, A lower bound for the depression of trees, Aus- tralas. J. Combin. 35 (2006) 319-328. Zbl1094.05018
- [10] T. Dzido and H. Furma´nczyk, Altitude of wheels and wheel-like graphs, Cent. Eur. J. Math. 8 (2010) 319-326. doi:10.7151/s11533-010-0017-4[WoS][Crossref] Zbl1205.05202
- [11] I. Gaber-Rosenblum and Y. Roditty, The depression of a graph and the diameter of its line graph, Discrete Math. 309 (2009) 1774-1778. doi:10.1016/j.disc.2008.03.002[Crossref][WoS] Zbl1205.05066
- [12] R.L. Graham and D.J. Kleitman, Increasing paths in edge ordered graphs, Period. Math. Hungar. 3 (1973) 141-148. doi:10.1007/BF02018469[Crossref] Zbl0243.05116
- [13] J. Katreniˇc and G. Semaniˇsin, Finding monotone paths in edge-ordered graphs, Dis- crete Appl. Math. 158 (2010) 1624-1632. doi:10.1016/j.dam.2010.05.018[Crossref]
- [14] C.M. Mynhardt, Trees with depression three, Discrete Math. 308 (2008) 855-864. doi:10.1016/j.disc.2007.07.039[Crossref][WoS]
- [15] C.M. Mynhardt, A.P. Burger and T.C. Clark, B. Falvai, and N.D.R. Henderson, Altitude of regular graphs with girth at least five, Discrete Math. 294 (2005) 241-257. doi:10.1016/j.disc.2005.02.007[Crossref] Zbl1062.05131
- [16] C.M. Mynhardt and M. Schurch, A class of graphs with depression three, Discrete Math. 313 (2013) 1224-1232. doi:10.1016/j.disc.2012.05.011[WoS][Crossref]
- [17] Y. Roditty, B. Shoham and R. Yuster, Monotone paths in edge-ordered sparse graphs, Discrete Math. 226 (2001) 411-417. doi:10.1016/S0012-365X(00)00174-6[Crossref] Zbl0961.05040
- [18] R. Yuster, Large monotone paths in graphs with bounded degree, Graphs Combin. 17 (2001) 579-587. doi:10.1007/s003730170031 [Crossref] Zbl1010.05044

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.