Return to search

On the Depression of Graphs

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

Identiferoai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/4527
Date17 April 2013
CreatorsSchurch, Mark
ContributorsMynhardt, C. M.
Source SetsUniversity of Victoria
LanguageEnglish, English
Detected LanguageEnglish
TypeThesis
RightsAvailable to the World Wide Web

Page generated in 0.0021 seconds