DIMACS TR: 2009-03
The cycle discrepancy of three regular graphs
Authors: Sarmad Abbasi and Laeeq Aslam
ABSTRACT
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.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2009/2009-03.pdf
DIMACS Home Page