DIMACS TR: 2009-03

The cycle discrepancy of three regular graphs

Authors: Sarmad Abbasi and Laeeq Aslam


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