Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCounting Hamiltonian cycles in planar triangulations
116
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
In 1930, Kuratowski showed that $K_{3,3}$ and $K_5$ are the only two minor-minimal non-planar graphs. Robertson and Seymour extended finiteness of the set of forbidden minors for any surface. v{S}ir{a}v{n} and Kochol showed that there are infinitely many $k$-crossing-critical graphs for any $kge 2$, even if restricted to simple $3$-connected graphs. Recently, $2$-crossing-critical graphs have been completely characterized by Bokal, Oporowski, Richter, and Salazar. We present a simplified description of large 2-crossing-critical graphs and use this simplification to count Hamiltonian cycles in such graphs. We generalize this approach to an algorithm counting Hamiltonian cycles in all 2-tiled graphs, thus extending the results of Bodrov{z}a-Pantic, Kwong, Doroslovav{c}ki, and Pantic for $n = 2$.
For a planar graph $H$, let $operatorname{mathbf{N}}_{mathcal P}(n,H)$ denote the maximum number of copies of $H$ in an $n$-vertex planar graph. In this paper, we prove that $operatorname{mathbf{N}}_{mathcal P}(n,P_7)sim{4over 27}n^4$, $operatorname{mathbf{N}}_{mathcal P}(n,C_6)sim(n/3)^3$, $operatorname{mathbf{N}}_{mathcal P}(n,C_8)sim(n/4)^4$ and $operatorname{mathbf{N}}_{mathcal P}(n,K_4{1})sim(n/6)^6$, where $K_4{1}$ is the $1$-subdivision of $K_4$. In addition, we obtain significantly improved upper bounds on $operatorname{mathbf{N}}_{mathcal P}(n,P_{2m+1})$ and $operatorname{mathbf{N}}_{mathcal P}(n,C_{2m})$ for $mgeq 4$. For a wide class of graphs $H$, the key technique developed in this paper allows us to bound $operatorname{mathbf{N}}_{mathcal P}(n,H)$ in terms of an optimization problem over weighted graphs.
A tight Hamilton cycle in a $k$-uniform hypergraph ($k$-graph) $G$ is a cyclic ordering of the vertices of $G$ such that every set of $k$ consecutive vertices in the ordering forms an edge. R{o}dl, Ruci{n}ski, and Szemer{e}di proved that for $kgeq 3$, every $k$-graph on $n$ vertices with minimum codegree at least $n/2+o(n)$ contains a tight Hamilton cycle. We show that the number of tight Hamilton cycles in such $k$-graphs is $exp(nln n-Theta(n))$. As a corollary, we obtain a similar estimate on the number of Hamilton $ell$-cycles in such $k$-graphs for all $ellin{0,dots,k-1}$, which makes progress on a question of Ferber, Krivelevich and Sudakov.
The problem of maximising the number of cliques among $n$-vertex graphs from various graph classes has received considerable attention. We investigate this problem for the class of $1$-planar graphs where we determine precisely the maximum total number of cliques as well as the maximum number of cliques of any fixed size. We also precisely characterise the extremal graphs for these problems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
