CYCLE DISCREPANCY OF GRAPHS

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