Marshall University Math Colloquium

January 25, 2012

“Cyclic Matching Sequencibility of Graphs.”

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.