No Arabic abstract
We introduce and study a $d$-dimensional generalization of Hamiltonian cycles in graphs - the Hamiltonian $d$-cycles in $K_n^d$ (the complete simplicial $d$-complex over a vertex set of size $n$). Those are the simple $d$-cycles of a complete rank, or, equivalently, of size $1 + {{n-1} choose d}$. The discussion is restricted to the fields $F_2$ and $Q$. For $d=2$, we characterize the $n$s for which Hamiltonian $2$-cycles exist. For $d=3$ it is shown that Hamiltonian $3$-cycles exist for infinitely many $n$s. In general, it is shown that there always exist simple $d$-cycles of size ${{n-1} choose d} - O(n^{d-3})$. All the above results are constructive. Our approach naturally extends to (and in fact, involves) $d$-fillings, generalizing the notion of $T$-joins in graphs. Given a $(d-1)$-cycle $Z^{d-1} in K_n^d$, ~$F$ is its $d$-filling if $partial F = Z^{d-1}$. We call a $d$-filling Hamiltonian if it is acyclic and of a complete rank, or, equivalently, is of size ${{n-1} choose d}$. If a Hamiltonian $d$-cycle $Z$ over $F_2$ contains a $d$-simplex $sigma$, then $Zsetminus sigma$ is a a Hamiltonian $d$-filling of $partial sigma$ (a closely related fact is also true for cycles over $Q$). Thus, the two notions are closely related. Most of the above results about Hamiltonian $d$-cycles hold for Hamiltonian $d$-fillings as well.
We show that the size of the largest simple d-cycle in a simplicial d-complex $K$ is at least a square root of $K$s density. This generalizes a well-known classical result of ErdH{o}s and Gallai cite{EG59} for graphs. We use methods from matroid theory applied to combinatorial simplicial complexes.
Hakimi, Schmeichel, and Thomassen in 1979 conjectured that every $4$-connected planar triangulation $G$ on $n$ vertices has at least $2(n-2)(n-4)$ Hamiltonian cycles, with equality if and only if $G$ is a double wheel. In this paper, we show that every $4$-connected planar triangulation on $n$ vertices has $Omega(n^2)$ Hamiltonian cycles. Moreover, we show that if $G$ is a $4$-connected planar triangulation on $n$ vertices and the distance between any two vertices of degree $4$ in $G$ is at least $3$, then $G$ has $2^{Omega(n^{1/4})}$ Hamiltonian cycles.
In 1999, Katona and Kierstead conjectured that if a $k$-uniform hypergraph $cal H$ on $n$ vertices has minimum co-degree $lfloor frac{n-k+3}{2}rfloor$, i.e., each set of $k-1$ vertices is contained in at least $lfloor frac{n-k+3}{2}rfloor$ edges, then it has a Hamiltonian cycle. R{o}dl, Ruci{n}ski and Szemer{e}di in 2011 proved that the conjecture is true when $k=3$ and $n$ is large. We show that this Katona-Kierstead conjecture holds if $k=4$, $n$ is large, and $V({cal H})$ has a partition $A$, $B$ such that $|A|=lceil n/2rceil$, $|{ein E({cal H}):|e cap A|=2}| <epsilon n^4$.
The Bubble-sort graph $BS_n,,ngeqslant 2$, is a Cayley graph over the symmetric group $Sym_n$ generated by transpositions from the set ${(1 2), (2 3),ldots, (n-1 n)}$. It is a bipartite graph containing all even cycles of length $ell$, where $4leqslant ellleqslant n!$. We give an explicit combinatorial characterization of all its $4$- and $6$-cycles. Based on this characterization, we define generalized prisms in $BS_n,,ngeqslant 5$, and present a new approach to construct a Hamiltonian cycle based on these generalized prisms.
In this series of papers, the primary goal is to enumerate Hamiltonian cycles (HCs) on the grid cylinder graphs $P_{m+1}times C_n$, where $n$ is allowed to grow whilst $m$ is fixed. In Part~I, we studied the so-called non-contractible HCs. Here, in Part~II, we proceed further on to the contractible case. We propose two different novel characterizations of contractible HCs, from which we construct digraphs for enumerating the contractible HCs. Given the impression which the computational data for $m leq 9$ convey, we conjecture that the asymptotic domination of the contractible HCs versus the non-contractible HCs, among the total number of HCs, depends on the parity of $m$.}