Friday, April 7, 2017
Grace McCourt Expands on 'Dishonest Salesperson Problem"
Because a profit is made on the mileage allowance, a salesperson wants to drive as far as possible during the trip, which financially benefits the salesperson at the loss of his or her employer, hence why the salesperson is being described as dishonest. As first posed and answered in Problem 1654 from Mathematics Magazine, the question is asked "What is the maximum possible distance he or she can travel on such a trip, and how many different such trips are there?" In her presentation, Grace will expand upon that result by using combinatorics and graph theory to derive results for the complete graph, in which each vertex is connect to each other vertex by exactly one edge, and the hypercube, which will be defined in the presentation. She will also present what is known for the cycle graph, the complete bipartite graph, and the complete m-ary tree of height h.