2016/09/30 by Ron Aharoni, Aharoni, Ron, Daniel Soltész +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1609.09746
arxiv created 2016/09/30 · arxiv updated 2016/10/03
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 ct such that for c<ct, f(n,cn) is bounded by a constant depending only on c and not on n, and for ct <c, f(n,cn) is exponentially large in n ~(n → ∞). We prove that 0.26 < ct < 0.36, but the exact value of ct 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 α(G)=n/4, then V(G) can be covered by vertex-disjoint K4 subgraphs.