Powers of Hamiltonian cycles in randomly augmented graphs

We study the existence of powers of Hamiltonian cycles in graphs with large minimum degree to which some additional edges have been added in a random manner. It follows from the theorems of Dirac and of Komlós, Sarközy, and Szemerédi that for every k ≥ 1 and sufficiently large n already the minimum degree for an n‐vertex graph G alone suffices to ensure the existence of a kth power of a Hamiltonian cycle. Here we show that under essentially the same degree assumption the addition of just O(n) random edges ensures the presence of the (k + 1)st power of a Hamiltonian cycle with probability close to one.     

On Hamiltonian bipartite graphs

Various sufficient conditions for the existence of Hamiltonian circuits in ordinary graphs are known. In this paper the analogous results for bipartite graphs are obtained.     

On k-ordered Hamiltonian graphs

A Hamiltonian graph G of order n is k-ordered, 2 ≤ k ≤ n, if for every sequence v₁, v₂, …, v_k of k distinct vertices of G, there exists a Hamiltonian cycle that encounters v₁, v₂, …, v_k in this order. Define f(k, n) as the smallest integer m for which any graph on n vertices with minimum degree at least m is a k-ordered Hamiltonian graph. In this article, answering a question of Ng and Schultz, we determine f(k, n) if n is sufficiently large in terms of k. Let g(k, n) = − 1. More precisely, we show that f(k, n) = g(k, n) if n ≥ 11k − 3. Furthermore, we show that f(k, n) ≥ g(k, n) for any n ≥ 2k. Finally we show that f(k, n) > g(k, n) if 2k ≤ n ≤ 3k − 6. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 17–25, 1999     

On certain Hamiltonian cycles in planar graphs

The problem is considered under which conditions a 4-connected planar or projective planar graph has a Hamiltonian cycle containing certain prescribed edges and missing certain forbidden edges. The results are applied to obtain novel lower bounds on the number of distinct Hamiltonian cycles that must be present in a 5-connected graph that is embedded into the plane or into the projective plane with face-width at least five. Especially, we show that every 5-connected plane or projective plane triangulation on n vertices with no non-contractible cyles of length less than five contains at least distinct Hamiltonian cycles. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 81–96, 1999     

On minimum degree in Hamiltonian path graphs

For integers p and s satisfying 2 ? s ? p ? 1, let m(p,s) denote the maximum number of edges in a graph G of order p such that the minimum degree in the hamiltonian path graph of G equals s. The values of m(p, s) are determined for 2 ? s ? p/2 and for (2p ? 2)/3 ? s ? p ? 1, and upper and lower bounds on m(p, s) are obtained for p/2 < s < (2p ? 2)/3.     

Hamiltonian pancyclic graphs

The class of 3-connected bipartite cubic graphs is shown to contain a non-Hamiltonian graph with only 78 vertices and to have a shortness exponent less than one.     

Hamiltonian path graphs

The Hamiltonian path graph H(G) of a graph G is that graph having the same vertex set as G and in which two vertices u and v are adjacent if and only if G contains a Hamiltonian u-v path. A characterization of Hamiltonian graphs isomorphic to their Hamiltonian path graphs is presented.     

k-ordered Hamiltonian graphs

A hamiltonian graph G of order n is k-ordered, 2 ≤ k ≤ n, if for every sequence v₁, v₂, …, v_k of k distinct vertices of G, there exists a hamiltonian cycle that encounters v₁, v₂, …, v_k in this order. Theorems by Dirac and Ore, presenting sufficient conditions for a graph to be hamiltonian, are generalized to k-ordered hamiltonian graphs. The existence of k-ordered graphs with small maximum degree is investigated; in particular, a family of 4-regular 4-ordered graphs is described. A graph G of order n ≥ 3 is k-hamiltonian-connected, 2 ≤ k ≤ n, if for every sequence v₁, v₂, …, v_k of k distinct vertices, G contains a v₁-v_k hamiltonian path that encounters v₁, v₂,…, v_k in this order. It is shown that for k ≥ 3, every (k + 1)-hamiltonian-connected graph is k-ordered and a result of Ore on hamiltonian-connected graphs is generalized to k-hamiltonian-connected graphs. © 1997 John Wiley & Sons, Inc.     

Hamiltonian threshold graphs

The vertices of a threshold graph G are partitioned into a clique K and an independent set I so that the neighborhoods of the vertices of I are totally ordered by inclusion. The question of whether G is hamiltonian is reduced to the case that K and I have the same size, say r, in which case the edges of K do not affect the answer and may be dropped from G, yielding a bipartite graph B. Let d₁≤d₂≤…≤d_r and e₁≤e₂≤…≤e_r be the degrees in B of the vertices of I and K, respectively. For each q = 0, 1,…,r−1, denote by S_q the following system of inequalities: d_j⩾j + 1, j = 1,2,…,q, e_j⩾j + 1, j = 1, 2,…, r−1−1. Then the following conditions are equivalent:

• 1.(1) B is hamiltonian,
• 2.(2) S_q holds for some q = 0, 1,…, r−1,
• 3.(3) S_q holds for each q = 0, 1,…, r−1.

     

Hamiltonian line graphs

Sufficient conditions on the degrees of a graph are given in order that its line graph have a hamiltonian cycle.     

ON THE CONSTRUCTION AND ENUMERATION OF HAMILTONIAN GRAPHS

In this paer we give a farmula for enumerating the equivalent classes of orderly labeled Hamiltonian graphs under group D.and two algorithms for constructing these equivalent classes and all nonisomorphic Hamiltonian graphs.Some computational results obtained by microcomputers are listed.     

Hamiltonian graphs involving distances

Let G be a graph of order n. We show that if G is a 2-connected graph and max{d(u), d(v)} + |N(u) U N(v)| ≥ n for each pair of vertices u, v at distance two, then either G is hamiltonian or G ?3K_n/3 U T₁ U T₂, where n ? O (mod 3), and T₁ and T₂ are the edge sets of two vertex disjoint triangles containing exactly one vertex from each K_n/3. This result generalizes both Fan's and Lindquester's results as well as several others.     

Hamiltonian uniform subset graphs

The uniform subset graph G(n, k, t) is defined to have all k-subsets of an n-set as vertices and edges joining k-subsets intersecting at t elements. We conjecture that G(n, k, t) is hamiltonian when it is different from the Petersen graph and does possess cycles. We verify this conjecture for k − t = 1, 2, 3 and for suitably large n when t = 0, 1.