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
|
Text
1609.09746v1.pdf Download (259kB) | Preview |
Abstract
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 |
SWORD Depositor: | MTMT SWORD |
Depositing User: | MTMT SWORD |
Date Deposited: | 28 Aug 2019 10:14 |
Last Modified: | 30 Sep 2021 02:05 |
URI: | http://real.mtak.hu/id/eprint/97054 |
Actions (login required)
![]() |
Edit Item |