dimacs logo

General Information

Jeremy Holden
CoRE 436
Norwich University
Faculty Advisor:
Ji Young Choi, Shippensburg University
The boundaries of the minimum Pk-total weights for simple connected graphs

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 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.

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),...