Abstract:
Let G=(V,E) be an undirected graph and C(G) denote the set of all cycles in G. We introduce a graph invariant, cycdisc(G), the cycle discrepancy of G, which is defined as
cycdisc(G) = \min_{\chi: V \mapsto \{+1, -1\}} \max_{ c \in C (G)} |\sum_{v \in c} \chi(v)|.
We show that, for n >= 6, if G is a theree regular graph with n vertices then
cycdisc(G) <= (n +2)/6.
This bound is best possible and is achieved by very simple graphs. Our proof is algorithmic and allows us to compute, in O(n^2) time, a labeling, \chi that
\max_{ c \in C(G)} | \sum_{v \in c} \chi(v)| <= (n + 2)/6.
Some interesting open problems regarding the cycle discrepancy are also suggested.
DIMACS Home Page