اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدCounting Hamiltonian cycles in planar triangulations
116
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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)$ Hamilton
ian 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 numb
er of cliques as well as the maximum number of cliques of any fixed size. We also precisely characterise the extremal graphs for these problems.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
