The sum of the weights on every path of length k in a graph with edges of weight 1 or -1 is called the Pk total weight of that labeling of the graph. The minimum of the absolute value of the Pk total weights of a graph over every possible ±1 labelings is called the minimum Pk total weight. The goal of my project is to study the boundaries of the minimum Pk total weights for simple, connected graphs.
As a related problem, I'm also very interested in discovering a method to find every path of length k in an arbitrary graph.