On Cycles that Alternate Through Selected Sets of Vertices
- PDF / 241,602 Bytes
- 7 Pages / 439.37 x 666.142 pts Page_size
- 74 Downloads / 185 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
On Cycles that Alternate Through Selected Sets of Vertices Colton Magnant1,2
•
Yaping Mao2,3
Received: 10 June 2019 / Revised: 3 May 2020 Springer Japan KK, part of Springer Nature 2020
Abstract Given two disjoint sets of k vertices each in a graph G, it was recently asked whether dðGÞ n=2 and jðGÞ 2k would be a sufficient assumption to guarantee the existence of a Hamiltonian cycle of G which alternates visiting vertices of the two selected sets. We answer this question in the affirmative when the graph is large and we also provide a generalization to more sets. Keywords Cycles Hamiltonian cycles Ordering vertices on cycles
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 ¼ fx1 ; x2 ; . . .; xk g, there is a cycle CS 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 CS that is also Hamiltonian (spanning the vertices of G). Originally defined in [5], there have been several results about k-ordered and kordered Hamiltonian graphs. One, in particular, that we will use is the following. Dedicated to the memory of Ralph Faudree, whose life and work inspired this and many other researchers. & Colton Magnant [email protected] Yaping Mao [email protected] 1
Department of Mathematics, Clayton State University, Morrow, GA 30260, USA
2
Academy of Plateau Science and Sustainability, Xining 810008, Qinghai, China
3
School of Mathematics and Statistics, Qinghai Normal University, Xining 810008, Qinghai, China
123
Graphs and Combinatorics
Theorem 1 ([2]) Let G be a graph on n vertices with minimum degree dðGÞ n=2 . Let k n=176 be an integer. If G is b3k=2c -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 [ 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 dðGÞ n=2 and jðGÞ 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 dðGÞ n=2 is required to guarantee that G is Hamiltonian and there is an easy example showing that jðGÞ 2k is necessary for a graph to contain an XY-altern
Data Loading...
