Marshall University Math Colloquium
January 25, 2012
Michael Schroeder
Marshall University
Abstract
Suppose you have 7 basketball teams in a round-robin tournament (each pair of teams play a game) and only one court. How can you schedule the games “fairly” for everyone? “Fair” is a vague term; when we say fair, we want all teams to have a maximal amount of down time between successive games (so no team plays two games in a row, for example). The answer to this question can be found using matching sequencibility.
Let G be a graph with m edges. Order the edges of G with the labels 1,2,…,m. The matching number of this ordering is the largest number d such that each consecutive d edges form a matching (don’t touch). The matching sequencibility (abbreviated ms) of G is the largest such d over all possible orderings of the edges. We will alter the premise a bit to talk about the cycle matching number of a graph ordering and define the cycle matching sequencibility (abbreviated cms) of a graph.