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$, $\{-1,1\}$ labels are assigned to the edges, and we consider a family ${\mathcal{S}}_G$ of (spanning) subgraphs of certain types, among others spanning trees, 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.

15 pages