Independent sets in the union of two Hamiltonian cycles

MaRDI QIDQ668015zbMATH OpenFDO

Authors Ron Aharoni, Daniel Soltész

Publication date 5 March 2019

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

Full work available at URL https://arxiv.org/abs/1609.09746, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p48

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

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)

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.

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.

Cites work

• scientific article; zbMATH DE number 3672329 (Why is no real title available?)
• scientific article; zbMATH DE number 3536160 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A note on Ramsey numbers
• Finding independent sets in \(K_4\)-free 4-regular connected graphs
• Kneser's conjecture, chromatic number, and homotopy
• The probabilistic method

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)