Search

We study how few longest cycles a regular graph can have under additional constraints. For each integer r ≥ 5 , we give exponential improvements for the best asymptotic upper bounds for this invariant under the additional constraint that the graphs are r -regular hamiltonian graphs. Earlier work showed that a conjecture by Haythorpe (2018) on a lower bound for this invariant is false because of an incorrect constant factor, whereas our results imply that the conjecture is even asymptotically incorrect. Motivated by a question of Zamfirescu (2022) and work of Chia and Thomassen (2012), we also study this invariant for non-hamiltonian 2-connected r -regular graphs and show that in this case the invariant can be bounded from above by a constant for all large enough graphs, even for graphs with arbitrarily large girth. [ABSTRACT FROM AUTHOR]

We confirm the following conjecture of Fekete and Woeginger from 1997: for any sufficiently large even number n, every set of n points in the plane can be connected by a spanning tour (Hamiltonian cycle) consisting of straight-line edges such that the angle between any two consecutive edges is at most π / 2 . Our proof is constructive and suggests a simple O (n log n) -time algorithm for finding such a tour. The previous best-known upper bound on the angle is 2 π / 3 , and it is due to Dumitrescu et al. (Electron. J. Comb. 19(2), # P31 (2012)). [ABSTRACT FROM AUTHOR]

In this paper we consider the following problem: Given a Hamiltonian graph G, and a Hamiltonian cycle C of G, can we compute a second Hamiltonian cycle C ′ ≠ C of G, and if yes, how quickly? If the input graph G satisfies certain conditions (e.g. if every vertex of G is odd, or if the minimum degree is large enough), it is known that such a second Hamiltonian cycle always exists. Despite substantial efforts, no subexponential-time algorithm is known for this problem. In this paper we relax the problem of computing a second Hamiltonian cycle in two ways. First, we consider approximating the length of a second longest cycle on n-vertex graphs with minimum degree δ and maximum degree Δ . We provide a linear-time algorithm for computing a cycle C ′ ≠ C of length at least n - 4 α (n + 2 α) + 8 , where α = Δ - 2 δ - 2 . This results provides a constructive proof of a recent result by Girão, Kittipassorn, and Narayanan in the regime of Δ δ = o (n) . Our second relaxation of the problem is probabilistic. We propose a randomized algorithm which computes a second Hamiltonian cycle with high probability, given that the input graph G has a large enough minimum degree. More specifically, we prove that for every 0 < p ≤ 0.02 , if the minimum degree of G is at least 8 p log 8 n + 4 , then a second Hamiltonian cycle can be computed with probability at least 1 - 1 n 50 p 4 + 1 in p o l y (n) · 2 4 p n time. This result implies that, when the minimum degree δ is sufficiently large, we can compute with high probability a second Hamiltonian cycle faster than any known deterministic algorithm. In particular, when δ = ω (log n) , our probabilistic algorithm works in 2 o (n) time. [ABSTRACT FROM AUTHOR]

In this paper, we consider covering graphs obtained by lifting a tree with a loop at each vertex as a voltage graph over a cyclic group. We generalize a tool of Hell et al. (2020), known as the billiard strategy, for constructing Hamiltonian cycles in the covering graphs of paths. We show that our extended tool can be used to provide new sufficient conditions for the Hamiltonicity of covering graphs of trees that are similar to those of Batagelj and Pisanski (1982) and of Hell et al. (2020). Next, we focus specifically on covering graphs obtained from trees lifted as voltage graphs over cyclic groups Z p of large prime order p. We prove that for a given reflexive tree T whose edge labels are assigned uniformly at random from a finite set, the corresponding lift is almost surely Hamiltonian for a large enough prime-ordered cyclic group Z p. Finally, we show that if a reflexive tree T is lifted over a group Z p of a large prime order, then for any assignment of nonzero elements of Z p to the edges of T , the corresponding cover of T has a large circumference. [ABSTRACT FROM AUTHOR]

Inspired by Sheehan's conjecture that no 4-regular graph contains exactly one hamiltonian cycle, we prove results on hamiltonian cycles in regular graphs and nearly regular graphs. We fully disprove a conjecture of Haythorpe on the minimum number of hamiltonian cycles in regular hamiltonian graphs, thereby extending a result of Zamfirescu, as well as correct and complement Haythorpe's computational enumerative results from [Exp. Math. 27 (2018), no. 4, 426–430]. Thereafter, we use the Lovász Local Lemma to extend Thomassen's independent dominating set method. This extension allows us to find a second hamiltonian cycle that inherits linearly many edges from the first hamiltonian cycle. Regarding the limitations of this method, we answer a question of Haxell, Seamone, and Verstraete, and settle the first open case of a problem of Thomassen by showing that for k \in \{5, 6\} there exist infinitely many k-regular hamiltonian graphs having no independent dominating set with respect to a prescribed hamiltonian cycle. Motivated by an observation of Aldred and Thomassen, we prove that for every \kappa \in \{ 2, 3 \} and any positive integer k, there are infinitely many non-regular graphs of connectivity \kappa containing exactly one hamiltonian cycle and in which every vertex has degree 3 or 2k. [ABSTRACT FROM AUTHOR]

In this paper, we consider a wireless sensor network consisting of an unmanned aerial vehicle (UAV) acting as a sink node and a number of sensor nodes scattered uncertainly on the ground. In the network, the UAV flies to a spatial point called point of interest and hovers to collect environmental data from neighboring sensor nodes. Then, the UAV proceeds to the next point of interest. The UAV must gather data from all the sensor nodes. On the other hand, a shorter round-trip air route of the UAV is more preferred since a battery-operated UAV needs regular recharging. To satisfy the requirement and to adhere to the recommendation as well, especially in the situation where only vague locational information about sensor nodes is available, we propose a scheme that follows three steps. First, it covers the sensor field of the wireless sensor network with three categories of hexagonal tessellations. Secondly, it establishes a point of interest at the centroid of each tile. Thirdly, it constructs an air route of the UAV, which visits every point of interest along a Hamiltonian cycle on the induced graph. Next, we develop a closed-form expression for the exact flight distance attained by the proposed scheme. For comparative evaluation, we discover some optimal schemes that minimize the flight distance by completely inspecting all patterns and corroborating the property of Hamiltonicity. The flight distance along the air route constructed by the proposed scheme is found to be only slightly longer than the flight distance yielded by an optimal scheme. Furthermore, the proposed scheme is proven to be practically valid when a common multicopter is employed as the sink node. [ABSTRACT FROM AUTHOR]

The prism over a graph G $G$ is the Cartesian product of G $G$ with the complete graph on two vertices. A graph G $G$ is prism‐hamiltonian if the prism over G $G$ is hamiltonian. We prove that every polyhedral graph (i.e., 3‐connected planar graph) of minimum degree at least four is prism‐hamiltonian. [ABSTRACT FROM AUTHOR]

For a finite group G, the superpower graph S(G) of G is an undirected simple graph with vertex set G and two vertices are adjacent in S(G) if and only if the order of one divides the order of the other in G. The aim of this paper is to provide tight bounds for the vertex connectivity, discuss Hamiltonian-like properties of superpower graph of finite non-Abelian groups having an element of exponent order.We also give some general results about superpower graphs and their relation to other graphs such as the Gruenberg–Kegel graph. [ABSTRACT FROM AUTHOR]

In this paper, we use theoretical and computational tools to continue our investigation of K2 ${K}_{2}$‐hamiltonian graphs, that is, graphs in which the removal of any pair of adjacent vertices yields a hamiltonian graph, and their interplay with K1 ${K}_{1}$‐hamiltonian graphs, that is, graphs in which every vertex‐deleted subgraph is hamiltonian. Perhaps surprisingly, there exist graphs that are both K1 ${K}_{1}$‐ and K2 ${K}_{2}$‐hamiltonian, yet non‐hamiltonian, for example, the Petersen graph. Grünbaum conjectured that every planar K1 ${K}_{1}$‐hamiltonian graph must itself be hamiltonian; Thomassen disproved this conjecture. Here we show that even planar graphs that are both K1 ${K}_{1}$‐ and K2 ${K}_{2}$‐hamiltonian need not be hamiltonian, and that the number of such graphs grows at least exponentially. Motivated by results of Aldred, McKay, and Wormald, we determine for every integer n $n$ that is not 14 or 17 whether there exists a K2 ${K}_{2}$‐hypohamiltonian, that is non‐hamiltonian and K2 ${K}_{2}$‐hamiltonian, graph of order n $n$, and characterise all orders for which such cubic graphs and such snarks exist. We also describe the smallest cubic planar graph which is K2 ${K}_{2}$‐hypohamiltonian, as well as the smallest planar K2 ${K}_{2}$‐hypohamiltonian graph of girth 5. We conclude with open problems and by correcting two inaccuracies from the first article. [ABSTRACT FROM AUTHOR]

In this paper we prove the following new sufficient condition for a digraph to be Hamiltonian: Let D be a 2-strong digraph of order n ≥ 9. If n − 1 vertices of D have degrees at least n + k and the remaining vertex has degree at least n − k − 4, where k is a non-negative integer, then D is Hamiltonian. This is an extension of Ghouila-Houri’s theorem for 2-strong digraphs and is a generalization of an early result of the author (DAN Arm. SSR (91(2):6-8, 1990). The obtained result is best possible in the sense that for k = 0 there is a digraph of order n = 8 (respectively, n = 9) with the minimum degree n − 4 = 4 (respectively, with the minimum degree n − 5 = 4) whose n − 1 vertices have degrees at least n − 1, but it is not Hamiltonian. We also give a new sufficient condition for a 3-strong digraph to be Hamiltonian-connected. [ABSTRACT FROM AUTHOR]

Let G = {Gi: i ∈ [n]} be a collection of not necessarily distinct n-vertex graphs with the same vertex set V, where G can be seen as an edge-colored (multi)graph and each Gi is the set of edges with color i. A graph F on V is called rainbow if any two edges of F come from different Gis'. We say that G is rainbow pancyclic if there is a rainbow cycle Cℓ of length ℓ in G for each integer ℓ ∈ [3, n]. In 2020, Joos and Kim proved a rainbow version of Dirac's theorem: If δ (G i) ≥ n 2 for each i ∈ [n], then there is a rainbow Hamiltonian cycle in G. In this paper, under the same condition, we show that G is rainbow pancyclic except that n is even and G consists of n copies of K n 2 , n 2 . This result supports the famous meta-conjecture posed by Bondy. [ABSTRACT FROM AUTHOR]

The Hamiltonian path is a well-known NP-complete problem. This problem has been studied for solid supergrid graphs, in some special cases, and recently for 3-connected solid supergrid graphs. In this paper, we extend the previous result to general solid supergrid graphs, and present an O(n²)-time algorithm where n is the number of the vertices of the input graph. [ABSTRACT FROM AUTHOR]

Diagnosis is an important technique for fault detection and location in interconnection network. The half hypercube, constructed from the hypercube, has been proven to possess several advantageous properties for interconnection networks, such as symmetry, smaller diameter, fewer edges and lower overhead. In this paper, we study the fault-tolerant embedding of Hamiltonian cycles and design an adaptive diagnosis algorithm for the half hypercube. Firstly, we prove that the half hypercube is Hamiltonian and propose an algorithm to construct a Hamiltonian cycle in the network. Furthermore, we prove that the half hypercube is Hamiltonian with no more than (⌈ n / 2 ⌉ - 1) faulty edges. Finally, we design a parallel adaptive diagnosis scheme under the PMC model, a system-level diagnosis model proposed by P, M, and C, which can identify almost all faulty vertices in five rounds. Simulation results demonstrate that the proposed algorithm is more effective, reducing running time by approximately 50% when compared to the Hamiltonian cycle embedding algorithm for the hypercube with the same dimension. [ABSTRACT FROM AUTHOR]

For a graph whose vertex set is a finite set of points in the Euclidean d -space consider the closed (open) balls with diameters induced by its edges. The graph is called a (an open) Tverberg graph if these closed (open) balls intersect. Using the idea of halving lines, we show that (i) for any finite set of points in the plane, there exists a Hamiltonian cycle that is a Tverberg graph; (ii) for any n red and n blue points in the plane, there exists a perfect red-blue matching that is a Tverberg graph. Also, we prove that (iii) for any even set of points in the Euclidean d -space, there exists a perfect matching that is an open Tverberg graph; (iv) for any n red and n blue points in the Euclidean d -space, there exists a perfect red-blue matching that is a Tverberg graph. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Xinjiang University (Natural Science Edition) is the property of Xinjiang University and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

We consider the class of 2-connected cubic graphs having only k-cycles in each 2-factor, and obtain the following two results: (i) every 2-connected cubic graph having only 8-cycles in each 2-factor is isomorphic to a unique Hamiltonian graph of order 8; and (ii) a 2-connected cubic planar graph G has only k-cycles in each 2-factor if and only if k = 4 and G is the complete graph of order 4. [ABSTRACT FROM AUTHOR]

In 2017, Adamus proved that a strong balanced bipartite digraph of order 2a with a ≥ 3 is hamiltonian, if d(u) + d(v) ≥ 3a for every pair of dominating or dominated vertices {u, v}. In this paper, we characterize all non-hamiltonian bipartite digraphs when d(u)+d(v) ≥ 3a-1 for every pair of dominating or dominated vertices {u, v}, consisting of one infinite family and four exceptional bipartite digraphs of order six. Using this result, we also prove that a strong balanced bipartite digraph of order 2a with a ≥ 4 contains all cycles of lengths 2, 4, . . ., 2a - 2 except for a single bipartite digraph, and also contains a hamiltonian path, if d(u) + d(v) ≥ 3a - 1 for every pair of dominating or dominated vertices {u, v}. The bounds for 3a-1 in two results are sharp. This partly settles the following problem when l = a-1 proposed by Adamus [A Meyniel-type condition for bipancyclicity in balanced bipartitie digraphs, Graphs Combin. 34 (2018) 703-709]. Whether for every 1 ≤ l < a there is a k(l), k(l) ≥ 1, such that every strong balanced bipartite digraph of order 2a contains cycles of lengths 2, 4, . . ., 2l, whenever d(u) + d(v) ≥ 3a - k(l) for every pair of dominating or dominated vertices {u, v}. [ABSTRACT FROM AUTHOR]

We study reconfiguration of simple Hamiltonian cycles in a rectangular grid graph G , where the Hamiltonian cycle in each step of the reconfiguration connects every internal vertex of G to a boundary vertex by a single straight line segment. We introduce two operations, flip and transpose, which are local to the grid. We show that any simple cycle of G can be reconfigured to any other simple cycle of G using O (| G |) flip and transpose operations. Our result proves that the simple Hamiltonian cycle graph  c y c is connected with respect to those two operations and has diameter O (| G |). [ABSTRACT FROM AUTHOR]

In this paper, we consider a wireless sensor network consisting of an unmanned aerial vehicle (UAV) acting as a sink node and a number of sensor nodes scattered uncertainly on the ground. In the network, the UAV flies to a spatial point called point of interest and hovers to collect environmental data from neighboring sensor nodes. Then, the UAV proceeds to the next point of interest. The UAV must gather data from all the sensor nodes. On the other hand, a shorter round-trip air route of the UAV is more preferred since a battery-operated UAV needs regular recharging. To satisfy the requirement and to adhere to the recommendation as well, especially in the situation where only vague locational information about sensor nodes is available, we propose a scheme that follows three steps. First, it covers the sensor field of the wireless sensor network with three categories of hexagonal tessellations. Secondly, it establishes a point of interest at the centroid of each tile. Thirdly, it constructs an air route of the UAV, which visits every point of interest along a Hamiltonian cycle on the induced graph. Next, we develop a closed-form expression for the exact flight distance attained by the proposed scheme. For comparative evaluation, we discover some optimal schemes that minimize the flight distance by completely inspecting all patterns and corroborating the property of Hamiltonicity. The flight distance along the air route constructed by the proposed scheme is found to be only slightly longer than the flight distance yielded by an optimal scheme. Furthermore, the proposed scheme is proven to be practically valid when a common multicopter is employed as the sink node.

A graph G is k-edge-Hamiltonian if any collection of vertex-disjoint paths with at most k edges altogether belong to a Hamiltonian cycle in G. A graph G is k-Hamiltonian if for all S ⊆ V (G) with | S | ≤ k , the subgraph induced by V (G) ∖ S has a Hamiltonian cycle. These two concepts are classical extensions of the usual Hamiltonian graphs. In this paper, we present some spectral sufficient conditions for a graph to be k-edge-Hamiltonian and k-Hamiltonian in terms of the adjacency spectral radius as well as the signless Laplacian spectral radius. Our results could be viewed as slight extensions of the recent theorems proved by Li and Ning [Linear Multilinear Algebra. 2016;64:2252–2269], Nikiforov [Czechoslovak Math J. 2016;66:925–940] and Li et al. [Linear Multilinear Algebra. 2018;66:2011–2023]. Moreover, we shall prove a stability result for graphs being k-Hamiltonian, which could be regarded as a complement of two recent results of Füredi et al. [Discrete Math. 2017;340:2688–2690] and [Discrete Math. 2019;342:1919–1923]. [ABSTRACT FROM AUTHOR]

Let G be a connected balanced bipartite graph of order 2 n ≥ 4 . Denote μ 2 (G) = min { d (x) + d (y) : x , y ∈ V (G) , dist (x , y) = 2 } . Some sufficient conditions for G to be hamiltonian or bipancyclic have been given in terms of vertex-degree and size of G. In this paper, we give a sufficient condition for vertex bipancyclicity of G. we show that if μ 2 (G) ≥ n + 2 , then each vertex of G is bipancyclic and the lower bound n + 2 is tight. [ABSTRACT FROM AUTHOR]

For a finite group G, and a subset S of G (possibly, contains the identity element), the bi-Cayley graph Bcay(G, S) of G with respect to S is defined as the undirected bipartite graph with vertex set G × { 0 , 1 } and edge set { { (g , 0) , (g s , 1) } | g ∈ G , s ∈ S } . In this paper, we give some sufficient conditions for the existence of hamiltonian cycle in Bcay (G = Z m ⋊ H , S) , where G = Z m ⋊ H is a semiproduct of Zm by a subgroup H of G. In addition, we introduce a new graph operation, which produces some classes of bi-Cayley graphs having hamiltonian cycle. [ABSTRACT FROM AUTHOR]

In this paper, we focus on Hamiltonian paths and Hamiltonian cycles passing through prescribed linear forests in n -dimensional star graph S n with fault-tolerant edges. Let F ⊆ E (S n) be a fault-tolerant edges set and L be a linear forest of S n − F , and | E (L) | + | F | ≤ n − 3. For any two vertices u and v in different partite sets, we prove that if { u , v } and L are compatible in S n , then there is a Hamiltonian path of S n − F between u and v , which passes through each edge of L. That is, S n is (n − 3) -edge fault-tolerant prescribed Hamiltonian laceable for n ≥ 4. And we show that there is a Hamiltonian cycle of S n − F passing through each edge of L , that is, S n is (n − 3) -edge fault-tolerant prescribed Hamiltonian for n ≥ 4. These results are optimal in the described sense. [ABSTRACT FROM AUTHOR]

For many algorithmic problems on graphs of treewidth t, a standard dynamic programming approach gives algorithms with time and space complexity 2O(t)\cdot nO(1). It turns out that when one considers the more restrictive parameter treedepth, it is often the case that a variation of this technique can be used to reduce the space complexity to polynomial, while retaining time complexity of the form 2O(d)\cdot nO(1), where d is the treedepth. This transfer of methodology is, however, far from automatic. For instance, for problems with connectivity constraints, standard dynamic programming techniques give algorithms with time and space complexity 2O(t)...nO(1) on graphs of treewidth t, but it is not clear how to convert them into time-efficient polynomial space algorithms for graphs of low treedepth. Cygan et al. [ACM Trans. Algorithms, 18 (2022), 17] introduced the Cut\&Count technique and showed that a certain class of problems with connectivity constraints can be solved in time and space complexity 2O(t) · nO(1). Recently, Hegerfeld and Kratsch (STACS'20) showed that, for some of those problems, the Cut\&Count technique can be also applied in the setting of treedepth, and it gives algorithms with running time 2O(d) · nO(1) and polynomial space usage. However, several important problems eluded such a treatment, with the most prominent examples being Hamiltonian Cycle and Longest Path. In this paper, we clarify the situation by showing that Hamiltonian cycle, Hamiltonian Path, Long Cycle, Long Path, and Min Cycle Cover all admit 5d · nO(1)-time and polynomial space algorithms on graphs of treedepth d. The algorithms are randomized Monte Carlo with only false negatives. [ABSTRACT FROM AUTHOR]

Signal optimisation is essential in traffic engineering. The traffic light control timings should be set as optimum. However, it is challenging because the traffic network is a non-polynomial problem. In this study, the problem is evaluated from a unique perspective. The primary idea is to remove the crossings of the intersections. A Hamiltonian cycle algorithm has been used to design the network. So, vehicles are only able to join or split. Thus, no control mechanism is needed that delays or interrupts the flow. The suggested algorithm and intersection design were tested on Allsop and Charlesworth's widely used sample network. Findings were compared with the literature in the form of delay calculated using the Highway Capacity Manual 2010 formula. The suggested network's delay is calculated to be 98.17% and 95.45% less than the original network and recently published study-based delay, respectively. As a result, Hamiltonian roads seem sustainable in time and fuel consumption and could be used for future designs. [ABSTRACT FROM AUTHOR]

Recently, the problem of counting Hamiltonian cycles in 2-tiled graphs was resolved by Vegi Kalamar, Bokal, and Žerak. In this paper, we continue our research on generalized tiled graphs. We extend algorithms on counting traversing Hamiltonian cycles from 2-tiled graphs to generalized tiled graphs. We further show that, similarly as for 2-tiled graphs, for a fixed finite set of tiles, counting traversing Hamiltonian cycles can be performed in linear time with respect to the size of such graph, implying that counting traversing Hamiltonian cycles in tiled graphs is fixed-parameter tractable. [ABSTRACT FROM AUTHOR]

The Hamiltonian cycle problem is one of the most important problems in graph theory that has many applications. This problem is NP-complete for general grid graphs. For solid grid graphs, there are polynomial-time algorithms. Existence of polynomial-time algorithms for grid graphs with few holes has been asked in the literature. In this paper, we give a linear-time algorithm for rectangular grid graphs with two rectangular holes. This extends the previous result for rectangular grid graphs with one rectangular hole. We first present the forbidden conditions in which there is no Hamiltonian cycle for any grid graphs, including rectangular grid graphs with rectangular holes. We then show that if these forbidden conditions do not hold, then there exists a Hamiltonian cycle. The proof is constructive, therefore, it gives an algorithm. An application of the problem is in off-line robot exploration. [ABSTRACT FROM AUTHOR]

A graph G $G$ is H $H$‐free if it has no induced subgraph isomorphic to H $H$, where H $H$ is a graph. In this paper, we show that every 32 $\frac{3}{2}$‐tough (P4∪P10) $({P}_{4}\cup {P}_{10})$‐free graph has a 2‐factor. The toughness condition of this result is sharp. Moreover, for any ε>0 $\varepsilon \gt 0$ there exists a (2−ε) $(2-\varepsilon)$‐tough 2P5 $2{P}_{5}$‐free graph without a 2‐factor. This implies that the graph P4∪P10 ${P}_{4}\cup {P}_{10}$ is best possible for a forbidden subgraph in a sense. [ABSTRACT FROM AUTHOR]

The Hamiltonian path and cycle problems are well-known NP-complete problems. A given graph is Hamiltonian-connected if there exists a Hamiltonian path between any two vertices and is Hamiltonian if it has a Hamiltonian cycle. In this paper, we show that every 3-connected solid supergrid graph is Hamiltonian-connected and every 2-connected solid supergrid graph is Hamiltonian, and give linear-time algorithms for computing Hamiltonian cycles and paths in these graphs. [ABSTRACT FROM AUTHOR]

We prove that a tournament T $T$ and its converse −T $-T$ contain the same number of oriented Hamiltonian paths and the same number of oriented Hamiltonian cycles, of any given type, as a generalization of Rosenfeld's result proved for antidirected paths. [ABSTRACT FROM AUTHOR]

The undirected power graph G (S) of a semigroup S is an undirected graph with vertex set S where two vertices u , v ∈ S are adjacent if and only if there is a positive integer m such that u m = v or v m = u . Here, we investigate the power graphs of a class of abelian groups and answer, in this case, the question whether or not the power graph is Hamiltonian. [ABSTRACT FROM AUTHOR]

Unlike the problem of finding Eulerian cycles, the problem of deciding whether a given graph has a Hamiltonian cycle is NP-complete, even when restricting to planar graphs. There are however some criteria that can be used in special cases. One of them can be derived by Grinberg's theorem. In this note, we give some more (slightly more general) criteria derived from Grinberg's theorem to show that a graph does not have a Hamiltonian cycle. [ABSTRACT FROM AUTHOR]

It has been conjectured there is a Hamiltonian cycle in every Cayley graph. Interest in this and other closely related questions has grown in the past few years. There have been many papers on the topic, but it is still an open question whether every connected Cayley graph has a Hamiltonian cycle. In this paper, we survey the results, techniques, and open problems in the field. [ABSTRACT FROM AUTHOR]

Let Cm and Cn be directed cycles of length m and n, with m; n ≥ 3, and let P(Cm □ Cn) be the digraph that is obtained from the Cartesian product Cm□Cn by choosing a vertex v, and reversing the orientation of all four directed edges that are incident with v. (This operation is called "pushing" at the vertex v.) By applying a special case of unpublished work of S. X.Wu, we find elementary numbertheoretic necessary and sufficient conditions for the existence of a hamiltonian cycle in P(Cm □ Cn). A consequence is that if P(Cm□ Cn) is hamiltonian, then gcd(m; n) = 1, which implies that Cm□ Cn is not hamiltonian. This final conclusion verifies a conjecture of J. B. Klerlein and E. C. Carr. [ABSTRACT FROM AUTHOR]

A graph G $G$ is called a 2K2 $2{K}_{2}$‐free graph if it does not contain 2K2 $2{K}_{2}$ as an induced subgraph. In 2014, Broersma, Patel, and Pyatkin showed that every 25‐tough 2K2 $2{K}_{2}$‐free graph on at least three vertices is Hamiltonian. Recently, Shan improved this result by showing that 3‐tough is sufficient instead of 25‐tough. In this paper, we show that every 2‐tough 2K2 $2{K}_{2}$‐free graph on at least three vertices is Hamiltonian, which was conjectured by Gao and Pasechnik. [ABSTRACT FROM AUTHOR]

Let G be a graph of even order and let K G be the complete graph on the same vertex set of G. A pairing of a graph G is a perfect matching of the graph K G. A graph G has the Pairing-Hamiltonian property (for short, the PH-property) if for each one of its pairings, there exists a perfect matching of G such that the union of the two gives rise to a Hamiltonian cycle of K G. In 2015, Alahmadi et al. gave a complete characterisation of the cubic graphs having the PH-property. Most naturally, the next step is to characterise the quartic graphs that have the PH-property. In this work we propose a class of quartic graphs on two parameters, n and k , which we call the class of accordion graphs A [ n , k ]. We show that an infinite family of quartic graphs (which are also circulant) that Alahmadi et al. stated to have the PH-property are, in fact, members of this general class of accordion graphs. We also study the PH-property of this class of accordion graphs, at times considering the pairings of G which are also perfect matchings of G. Furthermore, there is a close relationship between accordion graphs and the Cartesian product of two cycles. Motivated by a recent work by Bogdanowicz (2015), we give a complete characterisation of those accordion graphs that are circulant graphs. In fact, we show that A [ n , k ] is not circulant if and only if both n and k are even, such that k ≥ 4. [ABSTRACT FROM AUTHOR]

A well‐known conjecture of Alspach says that every 2k $2k$‐regular Cayley graph of a finite abelian group can be decomposed into Hamiltonian cycles. We consider an analogous question for infinite abelian groups. In this setting one natural analogue of a Hamiltonian cycle is a spanning double‐ray. However, a naive generalisation of Alspach's conjecture fails to hold in this setting due to the existence of 2k $2k$‐regular Cayley graphs with finite cuts F $F$, where ∣F∣ $| F| $ and k $k$ differ in parity, which necessarily preclude the existence of a decomposition into spanning double‐rays. We show that every 4‐regular Cayley graph of an infinite abelian group all of whose finite cuts are even can be decomposed into spanning double‐rays, and so characterise when such decompositions exist. We also characterise when such graphs can be decomposed either into Hamiltonian circles, a more topological generalisation of a Hamiltonian cycle in infinite graphs, or into a Hamiltonian circle and a spanning double‐ray. [ABSTRACT FROM AUTHOR]

We show that every claw-free cubic graph of order n at least 8 has at most 2⌊n4⌋{2^{\left\lfloor {{n \over 4}} \right\rfloor }} Hamiltonian cycles, and we also characterize all extremal graphs.

We study the embedding of the Hamiltonian Cycle problem, on a symmetric graph, in a discounted Markov decision process. The embedding allows us to explore the space of occupational measures corresponding to that decision process. In this paper we consider a convex combination of a Hamiltonian cycle and its reverse. We show that this convex combination traces out an interesting "H-curve" in the space of occupational measures. Since such an H-curve always exists in Hamiltonian graphs, its properties may help in differentiating between graphs possessing Hamiltonian cycles and those that do not. Our analysis relies on the fact that the resolvent-like matrix induced by our convex combination can be expanded in terms of finitely many powers of probability transition matrices corresponding to that Hamiltonian cycle. We derive closed form formulae for the coefficients of these powers which are reduced to expressions involving the classical Chebyshev polynomials of the second kind. For regular graphs, we also define a function that is the inner product of points on the H-curve with a suitably defined center of the space of occupational measures and show that, despite the nonlinearity of the inner-product, this function can be expressed as a linear function of auxiliary variables associated with our embedding. These results can be seen as stepping stones towards developing constraints on the space of occupational measures that may help characterize non-Hamiltonian graphs. [ABSTRACT FROM AUTHOR]

In this paper, we consider exploring a known rectangular cellular environment that has a rectangular obstacle using a mobile robot. The robot has to visit each cell and return to its starting cell. The goal is to find the shortest tour that visits all the cells. We give a linear-time algorithm that finds the exploration tour of optimal length. While the previous algorithms for environments with obstacles are approximation, the algorithm is presented in this paper is optimal. This algorithm also works for L-shaped and C-shaped environments. The main idea of the algorithm is, first, to find the longest simple exploring cycle, then extend it to include the unvisited cells. [ABSTRACT FROM AUTHOR]

What is the shape of the novel coronavirus (n-CoV) which has turned our world upside down? Even though under a microscope, it looks dull, unattractive, and even disgusting, creative artists have attributed to it bright colors, made it look pretty, and depicted it as a thing of beauty. What can a mathematician contribute to this effort? We take a purist's point of view by imposing on it a quasi-symmetry and then deriving some consequences. In an idealistic world, far removed from reality but still constrained by the rules of mathematics, anyone can enjoy this ethereal beauty of the mind's creation, beckoning others to join in the pleasure. Our musings end with this Part 4. We fondly hope readers have benefited from our suggestion that they indulge in their own musings, tell others about them, and propagate the good virus of mathematical thinking. [ABSTRACT FROM AUTHOR]