اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدCounting Hamiltonian cycles in 2-tiled graphs
107
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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$.
قيم البحث
اقرأ أيضاً
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 eve
ry $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 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
Barnettes conjecture is an unsolved problem in graph theory. The problem states that every 3-regular (cubic), 3-connected, planar, bipartite (Barnette) graph is Hamiltonian. Partial results have been derived with restrictions on number of vertices, s
everal properties of face-partitions and dual graphs of Barnette graphs while some studies focus just on structural characterizations of Barnette graphs. Noting that Spider web graphs are a subclass of Annular Decomposable Barnette (ADB graphs) graphs and are Hamiltonian, we study ADB graphs and their annular-connected subclass (ADB-AC graphs). We show that ADB-AC graphs can be generated from the smallest Barnette graph using recursive edge operations. We derive several conditions assuring the existence of Hamiltonian cycles in ADB-AC graphs without imposing restrictions on number of vertices, face size or any other constraints on the face partitions. We show that there can be two types of annuli in ADB-AC graphs, ring annuli and block annuli. Our main result is, ADB-AC graphs having non singular sequences of ring annuli are Hamiltonian.
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.
The toughness of a noncomplete graph $G$ is the maximum real number $t$ such that the ratio of $|S|$ to the number of components of $G-S$ is at least $t$ for every cutset $S$ of $G$, and the toughness of a complete graph is defined to be $infty$. Det
ermining the toughness for a given graph is NP-hard. Chv{a}tals toughness conjecture, stating that there exists a constant $t_0$ such that every graph with toughness at least $t_0$ is hamiltonian, is still open for general graphs. A graph is called $(P_3cup 2P_1)$-free if it does not contain any induced subgraph isomorphic to $P_3cup 2P_1$, the disjoint union of $P_3$ and two isolated vertices. In this paper, we confirm Chv{a}tals toughness conjecture for $(P_3cup 2P_1)$-free graphs by showing that every 7-tough $(P_3cup 2P_1)$-free graph on at least three vertices is hamiltonian.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
