On the discrepancies of graphs (Q2181999)

Summary: 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.