Independent sets in the union of two Hamiltonian cycles

Aharoni, Ron and Soltész, Dániel (2018) Independent sets in the union of two Hamiltonian cycles. ELECTRONIC JOURNAL OF COMBINATORICS, 25 (4). ISSN 1097-1440


Download (259kB) | Preview


Motivated by a question on the maximal number of vertex disjoint Schrijver graphs in the Kneser graph, we investigate the following function, denoted by f(n, k): the maximal number of Hamiltonian cycles on an n element set, such that no two cycles share a common independent set of size more than k. We shall mainly be interested in the behavior of f(n, k) when k is a linear function of n, namely k = cn. We show a threshold phenomenon: there exists a constant e t such that for c < c(t), f (n, cn) is bounded by a constant depending only on c and not on n, and for c(t) < c, f (n, cn) is exponentially large in n (n -> infinity). We prove that 0.26 < c(t) < 0.36, but the exact value of c(t) is not determined. For the lower bound we prove a technical lemma, which for graphs that are the union of two Hamiltonian cycles establishes a relation between the independence number and the number of K-4 subgraphs. A corollary of this lemma is that if a graph G on n > 12 vertices is the union of two Hamiltonian cycles and alpha(G) = n/4, then V (G) can be covered by vertex-disjoint K-4 subgraphs.

Item Type: Article
Additional Information: Funding Agency and Grant Number: BSF [2006099]; GIF grant [I -879 - 124.6/2005]; Technion's research promotion fund; Discont Bank chair; National Research, Development and Innovation Office NKFIH [K-120706, K-108947, KH-126853] Funding text: Supported by BSF grant no. 2006099, by GIF grant no. I -879 - 124.6/2005, by the Technion's research promotion fund, and by the Discont Bank chair.; Supported by the National Research, Development and Innovation Office NKFIH, No. K-120706, No. K-108947 and No. KH-126853
Subjects: Q Science / természettudomány > QA Mathematics / matematika
Depositing User: MTMT SWORD
Date Deposited: 28 Aug 2019 10:14
Last Modified: 28 Aug 2019 10:14

Actions (login required)

Edit Item Edit Item