TY - JOUR

T1 - Maximal sets of hamilton cycles in K2 p - F

AU - Fu, Hung-Lin

AU - Logan, S. L.

AU - Rodger, C. A.

PY - 2008/7/6

Y1 - 2008/7/6

N2 - A set S of edge-disjoint hamilton cycles in a graph T is said to be maximal if the hamilton cycles in S form a subgraph of T such that T - E (S) has no hamilton cycle. The spectrum of a graph T is the set of integers m such that T contains a maximal set of m edge-disjoint hamilton cycles. This spectrum has previously been determined for all complete graphs, all complete bipartite graphs, and many complete multipartite graphs. One of the outstanding problems is to find the spectrum for the graphs formed by removing the edges of a 1-factor, F, from a complete graph, K2 p. In this paper we completely solve this problem, giving two substantially different proofs. One proof uses amalgamations, and is of interest in its own right because it is the first example of an amalgamation where vertices from different parts are amalgamated. The other is a neat direct proof.

AB - A set S of edge-disjoint hamilton cycles in a graph T is said to be maximal if the hamilton cycles in S form a subgraph of T such that T - E (S) has no hamilton cycle. The spectrum of a graph T is the set of integers m such that T contains a maximal set of m edge-disjoint hamilton cycles. This spectrum has previously been determined for all complete graphs, all complete bipartite graphs, and many complete multipartite graphs. One of the outstanding problems is to find the spectrum for the graphs formed by removing the edges of a 1-factor, F, from a complete graph, K2 p. In this paper we completely solve this problem, giving two substantially different proofs. One proof uses amalgamations, and is of interest in its own right because it is the first example of an amalgamation where vertices from different parts are amalgamated. The other is a neat direct proof.

KW - Amalgamations

KW - Hamilton

KW - Maximal

UR - http://www.scopus.com/inward/record.url?scp=41549169109&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2006.09.059

DO - 10.1016/j.disc.2006.09.059

M3 - Article

AN - SCOPUS:41549169109

VL - 308

SP - 2822

EP - 2829

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 13

ER -