1 Introduction

In this paper, we consider only finite, simple, and undirected graphs. Unless otherwise defined, our notation follows that of [1]. A graph G is said to be k-ordered if, for any ordered set of k vertices \(S = \{x_{1}, x_{2}, \ldots , x_{k}\}\), there is a cycle \(C_{S}\) in G containing the vertices of S in order. Furthermore, G is said to be k-ordered Hamiltonian if for any ordered set S, there is such a cycle \(C_{S}\) that is also Hamiltonian (spanning the vertices of G).

Originally defined in [5], there have been several results about k-ordered and k-ordered Hamiltonian graphs. One, in particular, that we will use is the following.

Theorem 1

([2]) Let G be a graph on n vertices with minimum degree \(\delta (G) \ge n/2\). Let \(k \le n/176\)be an integer. If G is \(\left\lfloor 3k/2 \right\rfloor \)-connected, then G is k -ordered Hamiltonian. Furthermore the minimum degree and connectivity assumptions are best possible.

A slightly weaker concept than k-ordered is the notion of alternating between two sets of vertices. Given a graph G and two disjoint subsets X and Y of k vertices each, G is said to have an XY-alternating cycle (see [3]) if it contains a cycle C that visits all the vertices of \(X \cup Y\) in such a way that no pair of vertices of either set appear on the cycle without a vertex of the opposite set appearing in between. That is, the vertices of X and Y alternate around the cycle. Note that we make no claim about the order in which the individual vertices of X (or Y) appear along the cycle. In [3], Faudree et al. asked the following question.

Question 1

([3]) Are the conditions \(\delta (G) \ge n/2\)and \(\kappa (G) \ge 2k\)sufficient for the existence of an alternating Hamiltonian cycle for any subsets X and Y ?

Certainly these conditions would be the best possible since \(\delta (G) \ge n/2\) is required to guarantee that G is Hamiltonian and there is an easy example showing that \(\kappa (G) \ge 2k\) is necessary for a graph to contain an XY-alternating cycle for any choice of sets X and Y. We answer this question in the affirmative with the following result.

Theorem 2

Given a positive integer \(k \ge 2\) , an integer \(n \ge 352k\) , and a graph G of order n , if \(\delta (G) \ge n/2\) and \(\kappa (G) \ge 2k\) , then for any disjoint sets X and Y of k vertices each, G contains an XY -alternating Hamiltonian cycle. Furthermore the minimum degree and connectivity assumptions are best possible.

We will use the following result, which reduces the problem down to simply producing a cycle on which the vertices of X and Y alternate, as opposed to requiring that our cycle be Hamiltonian. Naturally, when this result is applied, we choose the set S to be \(S = X \cup Y\) with an ordering that alternates between X and Y.

Theorem 3

([2], Corollary 4) Let G be a graph on n vertices with minimum degree \(\delta (G) \ge n/2\). Let \(k < n/12\)be an integer, and let C be a cycle encountering a vertex sequence \(S = \{x_{1}, x_{2}, \ldots , x_{k}\}\)in the given order. If G is \(\left\lceil (k + 1)/2 \right\rceil \)-connected, then G has a Hamiltonian cycle encountering S in the given order.

One very natural question is what becomes of this type of alternating result when more sets of selected vertices are present. Suppose, for example, that we would like to find a cycle that alternates through three sets, X, Y, Z. In this case, we get the following result. Here we say a cycle is XYZ-alternating if it encounters one vertex of X, one of Y, one of Z, another from X and so on until all vertices of \(X \cup Y \cup Z\) have been included on the cycle. Notice that, by symmetry, the order of the sets does not matter so, for example, XYZ-alternating is the same as XZY-alternating.

Theorem 4

Given a positive integer \(k \ge 2\), an integer \(n \ge 528k\)and a graph G of order n , if \(\delta (G) \ge n/2\)and \(\kappa (G) \ge 3k\), then for any disjoint sets X, Y and Z of k vertices each, G contains an XYZ -alternating Hamiltonian cycle. Furthermore the minimum degree and connectivity assumptions are best possible.

We omit the proof of Theorem 4 since it is almost identical to the proof of Theorem 2.

More generally, we define alternating for more sets as an obvious extension of the previous definitions, that is, the cycle must visit one vertex from each set in the prescribed order.

Theorem 5

Given positive integers \(k \ge 2\) and \(m \ge 4\) , an integer \(n \ge 176mk\) and a graph G of order n , if \(\delta (G) \ge n/2\) and \(\kappa (G) \ge 2k\left\lfloor m/2 \right\rfloor + \left\lfloor km/2 \right\rfloor \) , then for any m disjoint sets \(X_{1}, X_{2}, \ldots , X_{m}\) of k vertices each, G contains an \(X_{1}X_{2}\ldots X_{m}\) -alternating cycle. Furthermore the minimum degree and connectivity assumptions are best possible.

The proof of Theorem 5 is also omitted as it is again very similar to the proof of Theorem 2.

The sharpness of the connectivity condition in this result follows from an example almost identical to the one presented in [2] to demonstrate the sharpness of Theorem 1. Let \(G = A \cup C \cup B\) where C is a complete graph on \(c = 2k\left\lfloor m/2 \right\rfloor - 1\) (one less than the first term of the assumed connectivity in Theorem 5) vertices and A and B are complete graphs on \(\left\lfloor (n - c)/2 \right\rfloor \) and \(\left\lceil (n - c)/2 \right\rceil \) vertices respectively. We also include all edges between A and C and between B and C. Select \(\left\lceil km/2 \right\rceil \) vertices of A and \(\left\lfloor km/2 \right\rfloor \) vertices of B to serve as our selected vertices \(X_{1}, X_{2}, \ldots , X_{m}\) so that \(X_{i} \subseteq A\) for all odd \(i < m\) and \(X_{j} \subseteq B\) for all even \(j \le m\) as well as (if m is odd) \(\left\lceil k/2 \right\rceil \) vertices of A for half of \(X_{m}\) and \(\left\lfloor k/2 \right\rfloor \) vertices of B for the other half. Finally we add all edges between these selected vertices except those between \(X_{i}\) and \(X_{i + 1}\) for all indices \(1 \le i \le m + 1\) where \(X_{m+1}\) is taken to mean \(X_{1}\). This graph has connectivity \(2k\left\lceil m/2 \right\rceil + \left\lfloor km/2 \right\rfloor - 1\) and cannot contain an \(X_{1}X_{2} \ldots X_{m}\)-alternating cycle since every path segment between vertices of the selected sets must use a vertex of C except one for each vertex of \(X_{m}\) when m is odd.

2 Proof of Theorem 2

Given a positive integer \(k \ge 2\), an integer \(n \ge 352k\), and a graph G of order n, suppose that \(\delta (G) \ge n/2\) and \(\kappa (G) \ge 2k\). Recall Theorem 2 claims that for any disjoint sets X and Y of k vertices each in G, then G contains an XY-alternating Hamiltonian cycle.

If \(\kappa (G) \ge 3k\), then we may apply Theorem 1 with \(S = X \cup Y\) ordered in such a way as to alternate between the sets X and Y to obtain the desired result. We may therefore assume that \(2k \le \kappa (G) < 3k\). Let C be a minimum cut set of G, so \(2k \le |C| < 3k\).

If there were at least 3 components in \(G{\setminus }C\), then one such component A must have order

$$\begin{aligned} |A| \le \frac{n - |C|}{3} < \frac{n}{3}. \end{aligned}$$

Each vertex in A must have degree at most \(|A| - 1 + |C| \le \frac{n}{3} + \frac{3n}{352}\). Since \(\delta (G) \ge n/2\) and \(n \ge 704\), this is a contradiction, meaning that there must be exactly two components, say \(A_{1}\) and \(A_{2}\), of \(G{\setminus }C\).

Given a subset \(S \subseteq V(G)\), let G[S] denote the subgraph of G induced on the set S. With \(\delta (G) \ge n/2\), we must have \(\delta (G[A_{i}]) \ge n/2 - |C| \ge n/2 - 3k + 1 \ge 173k\) for each \(i \in \{1, 2\}\). In particular, this implies that \(|A_{i}| \ge n/2 - 3k + 2\) so this means that

$$\begin{aligned} |A_{i}| = n - |A_{3 - i}| - |C| \le n/2. \end{aligned}$$

With \(n/2 - 3k + 2 \le |A_{i}| \le n/2\), and \(\delta (G[A_{i}]) \ge n/2 - 3k + 1\), we see that \(\delta (G[A_{i}]) \ge |A_{i}| - 3k + 1\) for each \(i \in \{1, 2\}\).

A graph H is called panconnected if between every pair of vertices \(u, v \in V(H)\), there is a path in H of every possible length from 2 up to \(|H| - 1\). A classical result of Williamson [6] states that any graph H with minimum degree at least \(\frac{|H| + 2}{2}\) is panconnected. Since, for each i, we have \(\delta (G[A_{i}]) \ge |A_{i}| - 3k + 1\) and \(|A_{i}| \ge 173k\), even if at most about 166k vertices are removed from \(A_{i}\), the graph induced on the remaining vertices would still be panconnected. This notion is formalized in the following fact.

Fact 1

For each \(i \in \{1, 2\}\), given any set S of at most 166k vertices with \(S \subseteq A_{i}\), the graph \(G[A_{i}{\setminus }S]\)is panconnected.

We intend to construct a cycle alternating through the sets X and Y using very few vertices from each set \(A_{i}\) at a time, always leaving behind a panconnected graph. Since we will only use at most about 12k vertices from each set \(A_{i}\), we may always apply Fact 1 at will within these sets.

For each i, we create new sets \(A_{i}'\) to contain \(A_{i}\) along with some vertices of C. For each vertex \(v \in C\), v gets included in \(A_{i}'\) if at least half of the edges from v to \(A_{1} \cup A_{2}\) go to \(A_{i}\). In this way, each vertex of C ends up in either \(A_{1}'\) or \(A_{2}'\). Then \(A_{1}'\) and \(A_{2}'\) partition V(G), that is \(V(G) = V(A_{1}') \cup V(A_{2}')\). An edge between \(A_{1}'\) and \(A_{2}'\) is called blocked if either both ends are in X or both ends are in Y. These blocked edges are restricted in how they can be used to create the desired alternating cycle. Call an edge from \(A_{1}'\) to \(A_{2}'\)free if it contains no edge of X or Y. Since \(\kappa (G) \ge 2k\), by Menger’s Theorem [4], there is a matching between \(A_{1}'\) and \(A_{2}'\) with at least 2k edges. Choose such a matching M with the minimum number of blocked edges. Call an edge from \(A_{1}'\) to \(A_{2}'\)covered if both ends are contained in \(X \cup Y\). Note that since M has at least 2k edges, there are at least as many free edges in M as there are covered edges of M.

For each vertex \(v \in C \cap A_{i}'\), choose a pair of distinct representatives \(v^{*}_{1}, v^{*}_{2} \in N(v) \cap A_{i}\). Such a system of distinct representatives can easily be chosen since each such vertex v must have at least \(\frac{n/2 - |C| + 1}{2} \ge 42k\) edges to \(A_{i}\) and \(|C| < 3k\) so fewer than 6k vertices appear as representatives.

In order to ensure that the edges of M are used as efficiently as possible, we must carefully prescribe (and minimize) when our constructed cycle must use an edge of M to move between \(A_{1}'\) and \(A_{2}'\). In particular, we must ensure effective use of those edges in M with exactly one vertex in \(X \cup Y\). Let \(T_{i}^{X}\) (and \(T_{i}^{Y}\)) be the vertices in \(X \cap M \cap A_{i}'\) (respectively \(Y \cap M \cap A_{i}'\)) for which the opposite end of the incident edge in M is not in \(X \cup Y\). These vertices have the flexibility to be used either as transportation to the opposite set \(A_{3 - i}'\) or staying within \(A_{i}'\). Let \(t_{i}^{X} = |T_{i}^{X}|\) and \(t_{i}^{Y} = |T_{i}^{Y}|\).

We now begin a process by which we paint paths between vertices of X and Y so that the union of these painted paths will be an XY-alternating cycle. First paint each edge of M which goes directly from a vertex of X to a vertex of Y. For each vertex v at either end of one of these painted edges, also paint the edge \(vv^{*}_{1}\). This results in some painted copies of \(P_{4}\) (centered around edges of M).

Next we count the number of edges incident with each vertex in \((X \cup Y) \cap A_{i}'\) (or their representatives) that are available for use in the painting process. For each vertex \(v \in X \cap A_{i}'\) (or respectively in \(Y \cap A_{i}'\)), if no edge incident to v has already been painted, we say that the X-weight of v is 2, or \(w_{X}(v) = 2\) (respectively \(w_{Y}(v) = 2\)). If two edges incident to v have already been painted, then we say the X-weight of \(v_{1}\) is 1, or \(w_{X}(v_{1}) = 1\) (respectively \(w_{Y}(v_{1}) = 1\)). Let \(x_{i}\) be the sum of the X-weights of vertices in \(A_{i}'\) and \(y_{i}\) be the sum of the Y-weights of vertices in \(A_{i}'\). That is, for example,

$$\begin{aligned} x_{i} = \sum _{v \in (X \cup Y) \cap A_{i}'} w_{X}(v) + w_{X}(v_{1}). \end{aligned}$$

Without loss of generality, suppose \(x_{1} \ge y_{1}\) (and so, by symmetry, \(x_{2} \le y_{2}\)). Select a set \(T \subseteq T_{1}^{X}\) of \(\min \{x_{i} - y_{i}, t_{1}^{X}\}\) vertices. For each vertex \(v \in T\), paint the incident edge of M and the edge \(vv_{1}\). Next we paint all edges of the form \(uu^{*}_{1}\) and \(uu^{*}_{2}\) for each \(u \in ((X \cup Y) \cap M) \setminus T\). Note that the set of all painted edges forms a linear forest. For the sake of notation, call these paths of painted edges the painted segments.

Arbitrarily choose a starting vertex from \(X \cup Y\), say \(v \in X \cap A_{i}\). If v has at least one painted edge, say to \(v^{*}_{1}\), we call \(v^{*}_{1}\) the current terminal vertex. Otherwise call v itself the current terminal vertex. The following is the process for painting the remainder of the desired alternating cycle:

Without loss of generality, suppose the current terminal vertex u is either in X or a representative of a vertex in X. Let \(i \in \{1, 2\}\) such that \(u \in A_{i}'\).

  • Suppose there is a vertex \(y \in Y \cap A_{i}\) which is not already on the painted path from the starting vertex to the current terminal vertex. Then by Fact 1, there is a path of length 2 from the current terminal vertex u to y. Paint this path and set y to be the current terminal vertex and repeat.

  • Suppose there is a vertex \(y \in Y \cap A_{i}' \cap M\) which is not already on the painted path from the starting vertex to the current terminal vertex. Then two edges incident to y are already painted, including the edge \(yy^{*}_{1}\). By Fact 1, there is a path of length 2 from the current terminal vertex u to \(y^{*}_{1}\). Paint this path. Let \(y'\) be the vertex at the opposite end of the painted segment containing y. Set \(y'\) to be the current terminal vertex and repeat.

  • Suppose there is no vertex \(y \in Y \cap A_{i}'\) which is not already on the painted path from the starting vertex to the current terminal vertex but there is such a vertex \(y \in A_{3 - i}'\).

    • If y has an incident painted edge of M, say to \(y' \notin X\), then by Fact 1, there is a path of length 2 from the current terminal vertex to \(y'\) (or perhaps to a representative of \(y'\), making a path of length 3 to \(y'\)). Paint this path. Let \(y^{\prime \prime }\) be the vertex at the opposite end of the painted segment containing y. Set \(y^{\prime \prime }\) to be the current terminal vertex and repeat.

    • If y has no incident painted edge of M, then arbitrarily select a free edge of M that has not already been painted. Such an edge must exist because \(|M| \ge 2k\) so there is a free edge of M for each vertex in \((X \cup Y) \cap (A_{1} \cup A_{2})\) and one for each pair of vertices in \(X \cup Y\) at either end of an edge in M. Letting ab be the selected free edge of M with \(a \in A_{i}'\), by Fact 1, there is a path of length 2 from the current terminal vertex to \(a_{1}\) (making a path of length 3 to a). Paint this path along with the edge ab. Similarly using Fact 1, we can find a path of length at most 4 between b and y in \(A_{3 - i}\) (perhaps through representatives of each). If y has no representatives, then set y to be the current terminal vertex and repeat. Otherwise, let \(y'\) be the vertex at the opposite end of the painted segment containing y. Set \(y'\) to be the current terminal vertex and repeat.

  • Finally suppose all vertices of \(X \cup Y\) are already on the painted path from the starting vertex to the current terminal vertex. Then again apply Fact 1, using a free edge of M if necessary, to create and paint a path from the current terminal vertex back to the starting vertex to complete the desired XY-alternating cycle.

Note that in the above process, in every bullet point, the painted path is getting strictly longer, meaning that the process will inevitably terminate at the final bullet point.

By Theorem 3, the existence of the constructed XY-alternating cycle guarantees the existence of an XY-alternating Hamiltonian cycle. This completes the proof of Theorem 2. \(\square \)

3 Conclusion

Using essentially the same proof, we can easily get the following result, another generalization of Theorems 2 and 4 to more sets. Here we say a cycle is \(X_{1}X_{2}\ldots X_{m}\)-mixed if it does not visit the same set twice without visiting a vertex from a different set first.

Theorem 6

Given positive integers \(k \ge 2\) and \(m \ge 2\) , an integer \(n \ge 176 km\) and a graph G of order n , if \(\delta (G) \ge n/2\) and \(\kappa (G) \ge km\) , then for any disjoint sets \(X_{1}X_{2} \ldots X_{m}\) of k vertices each, G contains a \(X_{1}X_{2} \ldots X_{m}\) -mixed Hamiltonian cycle. Furthermore the minimum degree and connectivity assumptions are best possible.