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

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 K4 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 vertexdisjoint K4 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 [K120706, K108947, KH126853] 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. K120706, No. K108947 and No. KH126853 
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:  28 Aug 2019 10:14 
URI:  http://real.mtak.hu/id/eprint/97054 
Actions (login required)
Edit Item 