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

Preview

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.

Actions (login required)

Edit Item