Booth Id:
MATH047
Category:
Year:
2016
Finalist Names:
Kumar, Agni
Abstract:
Network flow optimality on directed graphs is a central topic in graph theory and combinatorics. Given a complete graph G, we investigate the relationship between the score vectors of special tournaments on G and its spanning trees. Score vectors are assigned to tournaments on directed graphs in which the champion is a vertex A such that there is a directed path from A to every other vertex B. Comparing patterns examined between generated score vector sequences and parking functions, we define break divisors on complete graphs with n vertices to be n-tuples characterized by two distinct properties – one that defines the number of potential score vectors, and the other that accounts for impossible score sequences. We also show that these break divisors function as canonical representatives for each of the n^(n-2) linear equivalence classes of divisors of degree g on G. Specializing for complete graphs, we present an efficient algorithm for computing break divisors directly from spanning trees through the construction of partial graph orientations. This geometric bijection completes an alternate, unique proof of Arthur Cayley’s famous tree formula. The research results, particularly the concrete characterization of break divisors as mathematical tools to count and identify spanning trees and score vectors of tournaments with transitive champions, can have a multitude of applications to the development of Internet of Things frameworks.