Gray codes for -free strings.
Gray codes in graphs
Hamilton circuits with many colours in properly edge-coloured complete graphs.
Hamilton cycles in almost distance-hereditary graphs
Let G be a graph on n ≥ 3 vertices. A graph G is almost distance-hereditary if each connected induced subgraph H of G has the property dH(x, y) ≤ dG(x, y) + 1 for any pair of vertices x, y ∈ V(H). Adopting the terminology introduced by Broersma et al. and Čada, a graph G is called 1-heavy if at least one of the end vertices of each induced subgraph of G isomorphic to K1,3 (a claw) has degree at least n/2, and is called claw-heavy if each claw of G has a pair of end vertices with degree sum at least...
Hamilton cycles in split graphs with large minimum degree
A graph G is called a split graph if the vertex-set V of G can be partitioned into two subsets V₁ and V₂ such that the subgraphs of G induced by V₁ and V₂ are empty and complete, respectively. In this paper, we characterize hamiltonian graphs in the class of split graphs with minimum degree δ at least |V₁| - 2.
Hamilton decompositions of line graphs of some bipartite graphs
Some bipartite Hamilton decomposable graphs that are regular of degree δ ≡ 2 (mod 4) are shown to have Hamilton decomposable line graphs. One consequence is that every bipartite Hamilton decomposable graph G with connectivity κ(G) = 2 has a Hamilton decomposable line graph L(G).
Hamiltonian colorings of graphs with long cycles
By a hamiltonian coloring of a connected graph of order we mean a mapping of into the set of all positive integers such that (where denotes the length of a longest path in ) for all distinct . In this paper we study hamiltonian colorings of non-hamiltonian connected graphs with long cycles, mainly of connected graphs of order with circumference .
Hamiltonian connectedness and a matching in powers of connected graphs
In this paper the following results are proved: 1. Let be a path with vertices, where and . Let be a matching in . Then is hamiltonian-connected. 2. Let be a connected graph of order , and let be a matching in . Then is hamiltonian-connected.
Hamiltonian cycles and Hamiltonian-biconnectedness in bipartite digraphs.
Hamiltonian cycles in skirted trees
Hamiltonian lines in the square of graphs. I. Hamiltonian circuits in the square of cacti
Hamiltonian lines in the square of graphs. II
Hamiltonian paths on Platonic graphs.
Hamiltonian Simple Polytopes.
Hamiltonian virus-free digraphs.
Hamiltonian-colored powers of strong digraphs
For a strong oriented graph D of order n and diameter d and an integer k with 1 ≤ k ≤ d, the kth power of D is that digraph having vertex set V(D) with the property that (u, v) is an arc of if the directed distance from u to v in D is at most k. For every strong digraph D of order n ≥ 2 and every integer k ≥ ⌈n/2⌉, the digraph is Hamiltonian and the lower bound ⌈n/2⌉ is sharp. The digraph is distance-colored if each arc (u, v) of is assigned the color i where . The digraph is Hamiltonian-colored...
Hamiltonian-connected graphs and their strong closures.
Hamiltonicity exponent of digraphs.
Hamiltonicity in multitriangular graphs
The family of 5-valent polyhedral graphs whose faces are all triangles or 3s-gons, s ≥ 9, is shown to contain non-hamiltonian graphs and to have a shortness exponent smaller than one.
Hamiltonicity in Partly claw-free graphs
Matthews and Sumner have proved in [10] that if G is a 2-connected claw-free graph of order n such that δ(G) ≥ (n-2)/3, then G is Hamiltonian. We say that a graph is almost claw-free if for every vertex v of G, 〈N(v)〉 is 2-dominated and the set A of centers of claws of G is an independent set. Broersma et al. [5] have proved that if G is a 2-connected almost claw-free graph of order n such that n such that δ(G) ≥ (n-2)/3, then G is Hamiltonian. We generalize these results by considering the graphs...