On the number of hamiltonian cycles in a maximal planar graph

We consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph on p vertices. In particular, we construct a p-vertex maximal planar graph containing exactly four Hamiltonian cycles for every p ≥ 12. We also prove that every 4-connected maximal planar graph on p vertices contains at least p/(log₂ p) Hamiltonian cycles.     

Every connected,locally connected nontrivial graph with no induced claw is hamiltonian

A graph is locally connected if every neighborthood induces a connected subgraph. We show here that every connected, locally connected graph on p ≥ 3 vertices and having no induced K_1,3 is Hamiltonian. Several sufficient conditions for a line graph to be Hamiltonian are obtained as corollaries.     

An approximation algorithm for the hamiltonian walk problem on maximal planar graphs

A hamiltonian walk of a graph is a shortest closed walk that passes through every vertex at least once, and the length is the total number of traversed edges. The hamiltonian walk problem in which one would like to find a hamiltonian walk of a given graph is NP-complete. The problem is a generalized hamiltonian cycle problem and is a special case of the traveling salesman problem. Employing the techniques of divide-and-conquer and augmentation, we present an approximation algorithm for the problem on maximal planar graphs. The algorithm finds, in O(p²) time, a closed spanning walk of a given arbitrary maximal planar graph, and the length of the obtained walk is at most $\text{3}\text{2}$(p ? 3) if the graph has p (≥ 9) vertices. Hence the worst-case bound is $\text{3}\text{2}$.     

The circumference of the square of a connected graph

The celebrated result of Fleischner states that the square of every 2-connected graph is Hamiltonian. We investigate what happens if the graph is just connected. For every n ≥ 3, we determine the smallest length c(n) of a longest cycle in the square of a connected graph of order n and show that c(n) is a logarithmic function in n. Furthermore, for every c ≥ 3, we characterize the connected graphs of largest order whose square contains no cycle of length at least c.     

Toughness,trees, and walks

A graph is t‐tough if the number of components of G\S is at most |S|/t for every cutset S ⊆ V (G). A k‐walk in a graph is a spanning closed walk using each vertex at most k times. When k = 1, a 1‐walk is a Hamilton cycle, and a longstanding conjecture by Chvátal is that every sufficiently tough graph has a 1‐walk. When k ≥ 3, Jackson and Wormald used a result of Win to show that every sufficiently tough graph has a k‐walk. We fill in the gap between k = 1 and k ≥ 3 by showing that, when k = 2, every sufficiently tough (specifically, 4‐tough) graph has a 2‐walk. To do this we first provide a new proof for and generalize a result by Win on the existence of a k‐tree, a spanning tree with every vertex of degree at most k. We also provide new examples of tough graphs with no k‐walk for k ≥ 2. © 2000 John Wiley & Sons, Inc. J Graph Theory 33:125–137, 2000     

Hamiltonian paths in Cayley graphs

The classical question raised by Lovász asks whether every Cayley graph is Hamiltonian. We present a short survey of various results in that direction and make some additional observations. In particular, we prove that every finite group G has a generating set of size at most log₂|G|, such that the corresponding Cayley graph contains a Hamiltonian cycle. We also present an explicit construction of 3-regular Hamiltonian expanders.     

On Hamilton cycles in certain planar graphs

Let G be a 2-connected plane graph with outer cycle X_G such that for every minimal vertex cut S of G with |S| ≤ 3, every component of G\S contains a vertex of X_G. A sufficient condition for G to be Hamiltonian is presented. This theorem generalizes both Tutte's theorem that every 4-connected planar graph is Hamiltonian, as well as a recent theorem of Dillencourt about NST-triangulations. A linear algorithm to find a Hamilton cycle can be extracted from the proof. One corollary is that a 4-connected planar graph with the vertices of a triangle deleted is Hamiltonian. © 1996 John Wiley & Sons, Inc.     

The longest cycle of a graph with a large minimal degree

We show that every graph G on n vertices with minimal degree at least n/k contains a cycle of length at least [n/(k ? 1)]. This verifies a conjecture of Katchalski. When k = 2 our result reduces to the classical theorem of Dirac that asserts that if all degrees are at least 1/2n then G is Hamiltonian.     

On Hamiltonicity of 3-Connected Claw-Free Graphs

Lai, Shao and Zhan (J Graph Theory 48:142–146, 2005) showed that every 3-connected N ₂-locally connected claw-free graph is Hamiltonian. In this paper, we generalize this result and show that every 3-connected claw-free graph G such that every locally disconnected vertex lies on some induced cycle of length at least 4 with at most 4 edges contained in some triangle of G is Hamiltonian. It is best possible in some sense.     

One‐way infinite 2‐walks in planar graphs

We prove that every 3‐connected 2‐indivisible infinite planar graph has a 1‐way infinite 2‐walk. (A graph is 2‐indivisible if deleting finitely many vertices leaves at most one infinite component, and a 2‐walk is a spanning walk using every vertex at most twice.) This improves a result of Timar, which assumed local finiteness. Our proofs use Tutte subgraphs, and allow us to also provide other results when the graph is bipartite or an infinite analog of a triangulation: then the prism over the graph has a spanning 1‐way infinite path.     

Hamiltonian paths in vertex-symmetric graphs of order 4p

It is shown that every connected vertex-symmetric graph of order 4p (p a prime) has a Hamiltonian path.     

Dirac's theorem for random graphs

A classical theorem of Dirac from 1952 asserts that every graph on n vertices with minimum degree at least \begin{align*}\left\lceil n/2 \right\rceil\end{align*} is Hamiltonian. In this paper we extend this result to random graphs. Motivated by the study of resilience of random graph properties we prove that if p ? log n/n, then a.a.s. every subgraph of G(n,p) with minimum degree at least (1/2 + o (1) )np is Hamiltonian. Our result improves on previously known bounds, and answers an open problem of Sudakov and Vu. Both, the range of edge probability p and the value of the constant 1/2 are asymptotically best possible. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Bipartite graphs with cycles of all even lengths

Let G = (X, Y, E) be a bipartite graph with X = Y = n. Chvátal gave a condition on the vertex degrees of X and Y which implies that G contains a Hamiltonian cycle. It is proved here that this condition also implies that G contains cycles of every even length when n > 3.     

ℓ-distant Hamiltonian walks in Cartesian product graphs

We introduce and study a generalisation of Hamiltonian cycles: an ℓ-distant Hamiltonian walk in a graph G of order n is a cyclic ordering of its vertices in which consecutive vertices are at distance ℓ. Conditions for a Cartesian product graph to possess such an ℓ-distant Hamiltonian walk are given and more specific results are presented concerning toroidal grids.     

Hamilton paths and cycles in vertex-transitive graphs of order

It is shown that every connected vertex-transitive graph of order 6p, where p is a prime, contains a Hamilton path. Moreover, it is shown that, except for the truncation of the Petersen graph, every connected vertex-transitive graph of order 6p which is not genuinely imprimitive contains a Hamilton cycle.     

Minimum Degree Conditions for Cycles Including Specified Sets of Vertices

This paper generalises the concept of vertex pancyclic graphs. We define a graph as set-pancyclic if for every set S of vertices there is a cycle of every possible length containing S. We show that if the minimum degree of a graph exceeds half its order then the graph is set-pancyclic. We define a graph as k-ordered-pancyclic if, for every set S of cardinality k and every cyclic ordering of S, there is for every possible length a cycle of that length containing S and encountering S in the specified order. We determine the best possible minimum-degree condition which guarantees that a graph is k-ordered-pancyclic.     

Hamilton cycles in random graphs and directed graphs

We prove that almost every digraph D_{2–in, 2–out} is Hamiltonian. As a corollary we obtain also that almost every graph G_4–out is Hamiltonian. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 369–401, 2000     

3‐Factor‐Criticality of Vertex‐Transitive Graphs

A graph of order n is p ‐factor‐critical, where p is an integer of the same parity as n, if the removal of any set of p vertices results in a graph with a perfect matching. 1‐factor‐critical graphs and 2‐factor‐critical graphs are factor‐critical graphs and bicritical graphs, respectively. It is well known that every connected vertex‐transitive graph of odd order is factor‐critical and every connected nonbipartite vertex‐transitive graph of even order is bicritical. In this article, we show that a simple connected vertex‐transitive graph of odd order at least five is 3‐factor‐critical if and only if it is not a cycle.     

Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets

For every fixed graph H and every fixed 0 < α < 1, we show that if a graph G has the property that all subsets of size αn contain the “correct” number of copies of H one would expect to find in the random graph G(n,p) then G behaves like the random graph G(n,p); that is, it is p-quasi-random in the sense of Chung, Graham, and Wilson [4]. This solves a conjecture raised by Shapira [8] and solves in a strong sense an open problem of Simonovits and Sós [9].     

Pathwidth of outerplanar graphs

We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin [3], after having proved that the pathwidth of every biconnected outerplanar graph is always at most twice the pathwidth of its (geometric) dual plus two, conjectured that there exists a constant c such that the pathwidth of every biconnected outerplanar graph is at most c plus the pathwidth of its dual. They also conjectured that this was actually true with c being one for every biconnected planar graph. Fomin [10] proved that the second conjecture is true for all planar triangulations. First, we construct for each p ≥ 1, a biconnected outerplanar graph of pathwidth 2p + 1 whose (geometric) dual has pathwidth p + 1, thereby disproving both conjectures. Next, we also disprove two other conjectures (one of Bodlaender and Fomin [3], implied by one of Fomin [10]. Finally we prove, in an algorithmic way, that the pathwidth of every biconnected outerplanar graph is at most twice the pathwidth of its (geometric) dual minus one. A tight interval for the studied relation is therefore obtained, and we show that all cases in the interval happen. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 27–41, 2007