Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEnumeration of Hamiltonian Cycles on a Thick Grid Cylinder -- Part II: Contractible Hamiltonian Cycles
162
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$.}
rate research
Read More
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.
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.
Whitney proved in 1931 that 4-connected planar triangulations are Hamiltonian. Hakimi, Schmeichel, and Thomassen conjectured in 1979 that if $G$ is a 4-connected planar triangulation with $n$ vertices then $G$ contains at least $2(n-2)(n-4)$ Hamiltonian cycles, with equality if and only if $G$ is a double wheel. On the other hand, a recent result of Alahmadi, Aldred, and Thomassen states that there are exponentially many Hamiltonian cycles in 5-connected planar triangulations. In this paper, we consider 4-connected planar $n$-vertex triangulations $G$ that do not have too many separating 4-cycles or have minimum degree 5. We show that if $G$ has $O(n/{log}_2 n)$ separating 4-cycles then $G$ has $Omega(n^2)$ Hamiltonian cycles, and if $delta(G)ge 5$ then $G$ has $2^{Omega(n^{1/4})}$ Hamiltonian cycles. Both results improve previous work. Moreover, the proofs involve a double wheel structure, providing further evidence to the above conjecture.
We prove that if $G$ is a $k$-partite graph on $n$ vertices in which all of the parts have order at most $n/r$ and every vertex is adjacent to at least a $1-1/r+o(1)$ proportion of the vertices in every other part, then $G$ contains the $(r-1)$-st power of a Hamiltonian cycle
Let $G$ be a finite group. We show that if $|G| = pqrs$, where $p$, $q$, $r$, and $s$ are distinct odd primes, then every connected Cayley graph on $G$ has a hamiltonian cycle.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
