On the Discrepancies of Graphs

Abstract

In the literature, the notion of discrepancy is used in several contexts, even in the theory of graphs. Here, for a graph $G$ with each edge labelled $-1$ or $1$, we consider a family $\mathcal{S}_G$ of subgraphs of a certain type, such as spanning trees or Hamiltonian cycles. As usual, we seek for bounds on the sum of the labels that hold for all elements of $\mathcal{S}_G$, for every labeling.