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

Abstract

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

How to cite

top

Mark 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. [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. [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. [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. [4] G. Chartrand and L.M. Lesniak, Graphs and Digraphs (Third Ed.) (Wadsworth, 1996). 
  5. [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. [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. [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. [8] E.J. Cockayne and C.M. Mynhardt, Altitude of K3,n, J. Combin. Math. Combin. Comput. 52 (2005) 143-157. Zbl1073.05062
  9. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.