Independent sets in the union of two Hamiltonian cycles

zbMATH Open1409.05111arXiv1609.09746MaRDI QIDQ668015FDOQ668015

Authors: Ron Aharoni, Daniel Soltész 

Publication date: 5 March 2019

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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 $c_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(noinfty)$. 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.

Full work available at URL: https://arxiv.org/abs/1609.09746

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• On mutually independent Hamiltonian cycles.
• On independent cycles and edges in graphs
• Mutually independent Hamiltonian cycles in some graphs.
• Publication:3469119
• A note on neighborhood unions and independent cycles.

zbMATH Keywords

thresholdHamiltonian cycleindependent setunion

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Cites Work

• Title not available (Why is that?)
• Kneser's conjecture, chromatic number, and homotopy
• The probabilistic method
• Title not available (Why is that?)
• A note on Ramsey numbers
• Finding independent sets in \(K_4\)-free 4-regular connected graphs
• Title not available (Why is that?)

This page was built for publication: Independent sets in the union of two Hamiltonian cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q668015)