Abstract:
In this thesis a new graph invariant, cycle discrepancy, is introduced. The
optimal bounds on the cycle discrepancy for class of three-regular graphs and
class of 3-colorable graphs are found. If the class of three-regular graphs is
further restricted to Halin graphs, the established bound on cycle discrepancy
reduces linearly. Necessary and sufficient conditions are given for a
graph to have maximum possible cycle discrepancy. Further, it is shown
that computing cycle discrepancy of a graph is an NP-hard problem.
Let G = (V,E) be an undirected simple graph on n vertices. The
cycle discrepancy of G, denoted as cycdisc(G) is in general bounded as:
0 ≤ cycdisc(G) ≤ ⌈n
2
⌉. If G is a three colorable graph then cycdisc(G)
is tightly bounded by ⌊n
3
⌋. For d > 3, such d-colorable graphs are presented
that have maximum possible cycle discrepancy. If G is a cubic graph then
there is a tight bound of n+2
6 on its cycle discrepancy. An O(n2) algorithm
is also presented to label the vertices of G such that cycdisc(G) ≤ n+2
6 . If G
is not only cubic but also a Halin graph then cycdisc(G) ≤ n
8 +O(log n) and
this bound is tight apart from the additive O(log n) term.
It is also established that if minimum-degree of G is 3n
4 then cycdisc(G) =
⌈n
2
⌉. Further, for n > 6, if maximum-degree of G is Δ and Δ2 < n − 1, then
cycdisc(G) < ⌈n
2
⌉. A graph is also constructed with maximum-degree n
2 + 2,
that has maximum possible cycle discrepancy. This thesis provides a ground
for further investigation in this area.
ii
