A note on the cyclic matching sequencibility of graphs
Donald L. Kreher, Adrián Pastine, Leah Tollefson · Australas. J Comb. · 2015
In this note we present answers to the open problems posed by Brualdi, Kiernan, Meyer and Schroeder in [Cyclic matching sequencibility of graphs, Australas. J. Combin. 53 (2012), 245{256]. 1 Discussion and response Let G Kn be a graph of order n with m edges. The matching number of G is the maximum number of edges in a matching. The matching number of a linear ordering e1;e2;:::;em of the edges of G is the largest number d such that every d consecutive edges in the ordering form a d-matching of G. The matching sequencibility of G, denoted ms(G), is the maximum matching number of a linear ordering of the edges of G. The cyclic matching sequencibility of G, denoted cms(G), is the largest integer d such that there exists a cyclic ordering of the edges so that everyd consecutive edges in the ordering form a matching of G. In [1] Brualdi, Kiernan, Meyer, and Schroeder pose three questions concerning the relationship between ms(G) and cms(G). In this note we use the graph Yn in Figure 1 to provide answers to each of these questions. If G is any simple graph, kG denotes the multi-graph in which every edge of G is replicated k times.