Search

We adopt the recently introduced concept of the bipartite-hole-number due to McDiarmid and Yolov, and extend their result on Hamiltonicity to other Hamiltonian properties of graphs with a large minimum degree in terms of this concept. An (s, t)-bipartite-hole in a graph G consists of two disjoint sets of vertices S and T with |S| = s and |T| = t such that E(S, T) = ∅. The bipartite-hole-numbere ᾶ(G) is the maximum integer r such that G contains an (s, t)-bipartite-hole for every pair of nonnegative integers s and t with s + t = r. Our main results are that a graph G is traceable if δ(G) ≥ e ᾶ(G) - 1, and Hamilton-connected if δ(G) ≥ e ᾶ(G) + 1, both improving the analogues of Dirac's Theorem for traceable and Hamilton-connected graphs. [ABSTRACT FROM AUTHOR]

A graph G is called Hamilton-connected if for every pair of distinct vertices {u, v} of G there exists a Hamilton path in G that connects u and v. A graph G is said to be t-tough if t·ω(G − X) ≤ |X| for all X ⊆ V (G) with ω(G − X) > 1. The toughness of G, denoted τ (G), is the maximum value of t such that G is t-tough (taking τ (Kn) = ∞ for all n ≥ 1). It is known that a Hamilton-connected graph G has toughness τ (G) > 1, but that the reverse statement does not hold in general. In this paper, we investigate all possible forbidden subgraphs H such that every H-free graph G with τ (G) > 1 is Hamilton-connected. We find that the results are completely analogous to the Hamiltonian case: every graph H such that any 1-tough H-free graph is Hamiltonian also ensures that every H-free graph with toughness larger than one is Hamilton-connected. And similarly, there is no other forbidden subgraph having this property, except possibly for the graph K1 ∪ P4 itself. We leave this as an open case.

A graph is called Hamilton-connected if there exists a Hamiltonian path between every pair of its vertices. Determining whether or not a graph is Hamilton-connected is an NP-complete problem. In this paper, we present two methods to show Hamilton-connectivity in graphs. The first method uses the vertex connectivity and Hamiltoniancity of graphs, and, the second is the definition-based constructive method which constructs Hamiltonian paths between every pair of vertices. By employing these proof techniques, we show that the line graphs of the generalized Petersen, anti-prism and wheel graphs are Hamilton-connected. Combining it with some existing results, it shows that some of these families of Hamilton-connected line graphs have their underlying graph families non-Hamilton-connected. This, in turn, shows that the underlying graph of a Hamilton-connected line graph is not necessarily Hamilton-connected. As side results, the detour index being also an NP-complete problem, has been calculated for the families of Hamilton-connected line graphs. Finally, by computer we generate all the Hamilton-connected graphs on ≤ 7 vertices and all the Hamilton-laceable graphs on ≤ 10 vertices. Our research contributes towards our proposed conjecture that almost all graphs are Hamilton-connected. [ABSTRACT FROM AUTHOR]

In this paper, we have used two different proof techniques to show the Hamilton-connectedness of graphs. By using the vertex connectivity and Hamiltoniancity of graphs, we construct an infinite family of Hamilton-connected convex polytope line graphs whose underlying family of convex polytopes is not Hamilton-connected. By definition, we constructed two more infinite families of Hamilton-connected convex polytopes. As a by-product of our results, we compute exact values of the detour index of the families of Hamilton-connected convex polytopes. Finally, we classify the Platonic solids according to their Hamilton-connectedness and Hamilton-laceability properties.

A graph G is called Hamilton-connected if for every pair of distinct vertices fu; vg of G there exists a Hamilton path in G that connects u and v. A graph G is said to be t-tough if t · ω(G-X) ≤ |X| for all X ⊆ V (G) with ω(G-X) > 1. The toughness of G, denoted τ (G), is the maximum value of t such that G is t-tough (taking τ (Kn) = 1 for all n = 1). It is known that a Hamilton-connected graph G has toughness τ (G) > 1, but that the reverse statement does not hold in general. In this paper, we investigate all possible forbidden subgraphs H such that every H-free graph G with τ (G) > 1 is Hamilton-connected. We find that the results are completely analogous to the Hamiltonian case: every graph H such that any 1-tough H-free graph is Hamiltonian also ensures that every H-free graph with toughness larger than one is Hamilton-connected. And similarly, there is no other forbidden subgraph having this property, except possibly for the graph K1 [P4 itself. We leave this as an open case. [ABSTRACT FROM AUTHOR]

We present two new sufficient conditions in terms of the spectral radius ρ (G) guaranteeing that a k-connected graph G is Hamilton-connected, unless G belongs to a collection of exceptional graphs. We use the Bondy–Chvátal closure to characterize these exceptional graphs. [ABSTRACT FROM AUTHOR]

Chen et al. (1998) proved that every 18-tough chordal graph has a Hamilton cycle. Improving upon their bound, we show that every 10-tough chordal graph is Hamiltonian (in fact, Hamilton-connected). We use Aharoni and Haxell's hypergraph extension of Hall's Theorem as our main tool. [ABSTRACT FROM AUTHOR]

A collection of open problems that were posed at the 18th Workshop ‘3in1’, held on November 26-28, 2009 in Krakow, Poland. The problems are presented by Zdenek Ryjacek in “Does the Thomassen's conjecture imply N=NP?” and “Dominating cycles and hamiltonian prisms”, and by Carol T. Zamfirescu in “Two problems on bihomogeneously traceable digraphs”.

An arc of a graph is an oriented edge and a 3-arc is a 4-tuple ( v, u, x, y) of vertices such that both ( v, u, x) and ( u, x, y) are paths of length two. The 3-arc graph of a graph G is defined to have vertices the arcs of G such that two arcs uv, xy are adjacent if and only if ( v, u, x, y) is a 3-arc of G. We prove that any connected 3-arc graph is hamiltonian, and all iterative 3-arc graphs of any connected graph of minimum degree at least three are hamiltonian. As a corollary we obtain that any vertex-transitive graph which is isomorphic to the 3-arc graph of a connected arc-transitive graph of degree at least three must be hamiltonian. This confirms the conjecture, for this family of vertex-transitive graphs, that all vertex-transitive graphs with finitely many exceptions are hamiltonian. We also prove that if a graph with at least four vertices is Hamilton-connected, then so are its iterative 3-arc graphs. [ABSTRACT FROM AUTHOR]

Abstract: The square of a graph is the graph having the same vertex set as and two vertices are adjacent if and only if they are at distance at most 2 from each other. It is known that if has no cut-vertex, then is Hamilton-connected (see [G. Chartrand, A.M. Hobbs, H.A. Jung, S.F. Kapoor, C.St.J.A. Nash-Williams, The square of a block is hamiltonian connected, J. Combin. Theory Ser. B 16 (1974) 290–292; R.J. Faudree and R.H. Schelp, The square of a block is strongly path connected, J. Combin. Theory Ser. B 20 (1976) 47–61]). We prove that if has only one cut-vertex, then is Hamilton-connected. In the case that has only two cut-vertices, we prove that if the block that contains the two cut-vertices is hamiltonian, then is Hamilton-connected. Further, we characterize all graphs with at most one cycle having Hamilton-connected square. [Copyright &y& Elsevier]