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 the +/- 1-assigned graph. The minimum of the absolute value of the Pk-total weights of a graph considering every possible +/- 1 assignment is called the minimum Pk-total weight. This project is to study the boundaries of the minimum Pk-total weights for simple connected graphs.
Here is a PowerPoint presentation that demonstrates a few computations: Presentation
If you are interested in this, feel free to e-mail me with questions or comments. Proofs of results listed below can be provided on request.
Familiarized self with problem.
Computed many small examples.
Reduced the problem of computing Pk(Kn) to counting the number of trails involving a single edge
Found general formulas for P1(Kn), P2(Kn),...,P4(Kn)
Pk(Kn) = 0 for n=0,1(mod4) from symmetry
Worked on a general formula for Pk(Kn) (no success yet)
Found a necessary and sufficient condition for Pk(G) = 0.
Found a symmetrical expansion technique to inflate an arbitrary graph G into a new graph H with Pk(H) = 0 for all k.
Computed much of Pk(K6)
Attempted to find a unimodality proof for the sequence P1(Kn), P2(Kn),...