An edge ordering of a graph G = (V,E) is an injection f : E → R, where R denotes
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. In this dissertation we
discuss various results relating to the depression of a graph. We determine a formula
for the depression of the class of trees known as double spiders. 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.
We study the concept of k-kernels and discuss related depression results, including
an improved upper bound for the depression of trees. We include a characterization
of the class of graphs with depression three and without adjacent vertices of degree
three or higher, and also construct a large class of graphs with depression three which
contains graphs with adjacent vertices of high degree. Lastly, we apply the concept
of ascents to edge colourings using possibly fewer than |E(G)| colours (integers). We
consider the problem of determining the minimum number of colours for which there
exists an edge colouring such that the length of a shortest maximal path of edges
with increasing colors has a given length. / Graduate / 0405
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/4527 |
| Date | 17 April 2013 |
| Creators | Schurch, Mark |
| Contributors | Mynhardt, C. M. |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | Available to the World Wide Web |
Page generated in 0.0021 seconds