Directed and antidirected Hamiltonian cycles and paths in bipartite graphs
Edge-disjoint Hamilton cycles in 4-regular planar graphs.
Edge-disjoint Hamiltonian cycles in two-dimensional torus.
Ein planarer hypohamiltonscher Graph mit 57 Knoten.
Embeddings of hamiltonian paths in faulty k-ary 2-cubes
It is well known that the k-ary n-cube has been one of the most efficient interconnection networks for distributed-memory parallel systems. A k-ary n-cube is bipartite if and only if k is even. Let (X,Y) be a bipartition of a k-ary 2-cube (even integer k ≥ 4). In this paper, we prove that for any two healthy vertices u ∈ X, v ∈ Y, there exists a hamiltonian path from u to v in the faulty k-ary 2-cube with one faulty vertex in each part.
Enumerating all Hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs.
Enumeration of Hamiltonian circuits in rectangular grids.
Enumeration of hamiltonian paths in Caley diagrams.
Equations relating factors in decompositions into factors of some family of plane triangulations, and applications (with an appendix by Andrzej Schinzel)
Let be the family of all 2-connected plane triangulations with vertices of degree three or six. Grünbaum and Motzkin proved (in dual terms) that every graph P ∈ has a decomposition into factors P₀, P₁, P₂ (indexed by elements of the cyclic group Q = 0,1,2) such that every factor consists of two induced paths of the same length M(q), and K(q) - 1 induced cycles of the same length 2M(q). For q ∈ Q, we define an integer S⁺(q) such that the vector (K(q),M(q),S⁺(q)) determines the graph P (if P is...
Extension of several sufficient conditions for Hamiltonian graphs
Let G be a 2-connected graph of order n. Suppose that for all 3-independent sets X in G, there exists a vertex u in X such that |N(X∖u)|+d(u) ≥ n-1. Using the concept of dual closure, we prove that 1. G is hamiltonian if and only if its 0-dual closure is either complete or the cycle C₇ 2. G is nonhamiltonian if and only if its 0-dual closure is either the graph , 1 ≤ r ≤ s ≤ t or the graph . It follows that it takes a polynomial time to check the hamiltonicity or the nonhamiltonicity of a graph...
Extremal problems for forbidden pairs that imply hamiltonicity
Let C denote the claw , N the net (a graph obtained from a K₃ by attaching a disjoint edge to each vertex of the K₃), W the wounded (a graph obtained from a K₃ by attaching an edge to one vertex and a disjoint path P₃ to a second vertex), and the graph consisting of a K₃ with a path of length i attached to one vertex. For k a fixed positive integer and n a sufficiently large integer, the minimal number of edges and the smallest clique in a k-connected graph G of order n that is CY-free (does...
Factors and circuits in -free graphs
Families of triples with high minimum degree are hamiltonian
In this paper we show that every family of triples, that is, a 3-uniform hypergraph, with minimum degree at least [...] contains a tight Hamiltonian cycle
Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs
A graph G is said to be 1-tough if for every vertex cut S of G, the number of components of G − S does not exceed |S|. Being 1-tough is an obvious necessary condition for a graph to be hamiltonian, but it is not sufficient in general. We study the problem of characterizing all graphs H such that every 1-tough H-free graph is hamiltonian. We almost obtain a complete solution to this problem, leaving H = K1 ∪ P4 as the only open case.
Forbidden triples implying Hamiltonicity: for all graphs
In [2], Brousek characterizes all triples of graphs, G₁, G₂, G₃, with for some i = 1, 2, or 3, such that all G₁G₂G₃-free graphs contain a hamiltonian cycle. In [6], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁, G₂, G₃, none of which is a , s ≥ 3 such that G₁, G₂, G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In this paper, a characterization will be given of all triples G₁, G₂, G₃ with none being , such that all G₁G₂G₃-free...
From L. Euler to D. König
Starting from the famous Königsberg bridge problem which Euler described in 1736, we intend to show that some results obtained 180 years later by König are very close to Euler's discoveries.
Generating hamiltionian cycles in complete graphs.
Graph invariants and large cycles: a survey.
Graphs maximal with respect to absence of hamiltonian paths
Two classes of graphs which are maximal with respect to the absence of Hamiltonian paths are presented. Block graphs with this property are characterized.
Graphs and a variant of the Tower of Hanoi problem
For any and any , a graph is introduced. Vertices of are -tuples over and two -tuples are adjacent if they are in a certain relation. These graphs are graphs of a particular variant of the Tower of Hanoi problem. Namely, the graphs are isomorphic to the graphs of the Tower of Hanoi problem. It is proved that there are at most two shortest paths between any two vertices of . Together with a formula for the distance, this result is used to compute the distance between two vertices in...