On the discrepancies of graphs

2020/02/26 by Balogh, József, Csaba, Béla, Jing, Yifan +1 · 2 citations
#05C35 #05D10 #11K38 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2002.11793

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 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 S_G, for every labeling.

Cited by

• Colour-biased Hamilton cycles in dense graphs and random graphs
• Optimal stability results on color-biased Hamilton cycles

Related

• Discrepancies of Spanning Trees and Hamilton Cycles
• Note on the group edge irregularity strength of graphs
• On the Graham--Sloane harmonious labelling conjecture
• Graphs without gap-vertex-labellings: families and bounds
• Spanning F-cycles in random graphs