General Information
Project Description
The sum of the weights on every path of length k in a graph with edges of weight 1 or 1 is called the Pktotal weight of the +/ 1assigned graph. The minimum of the absolute value of the Pktotal weights of a graph considering every possible +/ 1 assignment is called the minimum Pktotal weight. This project is to study the boundaries of the minimum Pktotal 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 email me with questions or comments. Proofs of results listed below can be provided on request.
Project Log
Week 1
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
Week 2
Found P5(Kn)
Worked on a general formula for Pk(Kn) (no success yet)
Found a necessary and sufficient condition for Pk(G) = 0.
Week 3
Found a symmetrical expansion technique to inflate an arbitrary graph G into a new graph H with Pk(H) = 0 for all k.
Found P6(Kn)
Computed much of Pk(K6)
Attempted to find a unimodality proof for the sequence P1(Kn), P2(Kn),...
