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 SG 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 SG, for every labeling.
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics