The Hamiltonian connectivity of rectangular supergrid graphs

A Hamiltonian path of a graph is a simple path which visits each vertex of the graph exactly once. The Hamiltonian path problem is to determine whether a graph contains a Hamiltonian path. A graph is called Hamiltonian connected if there exists a Hamiltonian path between any two distinct vertices. In this paper, we will study the Hamiltonian connectivity of rectangular supergrid graphs. Supergrid graphs were first introduced by us and include grid graphs and triangular grid graphs as subgraphs. The Hamiltonian path problem for grid graphs and triangular grid graphs was known to be NP-complete. Recently, we have proved that the Hamiltonian path problem for supergrid graphs is also NP-complete. The Hamiltonian paths on supergrid graphs can be applied to compute the stitching traces of computer sewing machines. Rectangular supergrid graphs form a popular subclass of supergrid graphs, and they have strong structure. In this paper, we provide a constructive proof to show that rectangular supergrid graphs are Hamiltonian connected except one trivial forbidden condition. Based on the constructive proof, we present a linear-time algorithm to construct a longest path between any two given vertices in a rectangular supergrid graph.     

A successful algorithm for solving directed Hamiltonian path problems

In this paper we present a graph-theoretic polynomial algorithm which has positive probability of finding a Hamiltonian path in a given graph, if there is one; if the algorithm fails, it can be rerun with a randomly chosen starting solution, and there is again a positive probability it will find an answer. If there is no Hamiltonian path, the algorithm will always terminate with failure. We call this a Successful Algorithm because it has high (close to 1) empirical probability of success and it works in polynomial time. Some basic theoretical results concerning spanning arborescences of a graph are given. The concept of a ramification index is defined and it is shown that ramification index of a Hamiltonian path is zero. The algorithm starts with finding any spanning arborescence and by suitable pivots it endeavors to reduce the ramification index to zero. Probabilistic properties of the algorithm are discussed. Computational experience with graphs up to 30 000 nodes is included.     

Tricylic hamiltonian graphs with minimal index

The index of a graph is the largest eigenvalue of an adjacency matrix whose entries are the real numbers 0 and 1. Among the tricyclic Hamiltonian graphs with a prescribed number of vertices, those graphs with minimal index are determined.     

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.     

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     

Tricylic hamiltonian graphs with minimal index

The index of a graph is the largest eigenvalue of an adjacency matrix whose entries are the real numbers 0 and 1. Among the tricyclic Hamiltonian graphs with a prescribed number of vertices, those graphs with minimal index are determined.     

Small Spectral Gap in the Combinatorial Laplacian Implies Hamiltonian

We consider the spectral and algorithmic aspects of the problem of finding a Hamiltonian cycle in a graph. We show that a sufficient condition for a graph being Hamiltonian is that the nontrivial eigenvalues of the combinatorial Laplacian are sufficiently close to the average degree of the graph. An algorithm is given for the problem of finding a Hamiltonian cycle in graphs with bounded spectral gaps which has complexity of order n ^{cln n} .     

A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem

In this paper, we propose a new hybrid algorithm for the Hamiltonian cycle problem by synthesizing the Cross Entropy method and Markov decision processes. In particular, this new algorithm assigns a random length to each arc and alters the Hamiltonian cycle problem to the travelling salesman problem. Thus, there is now a probability corresponding to each arc that denotes the probability of the event “this arc is located on the shortest tour.” Those probabilities are then updated as in cross entropy method and used to set a suitable linear programming model. If the solution of the latter yields any tour, the graph is Hamiltonian. Numerical results reveal that when the size of graph is small, say less than 50 nodes, there is a high chance the algorithm will be terminated in its cross entropy component by simply generating a Hamiltonian cycle, randomly. However, for larger graphs, in most of the tests the algorithm terminated in its optimization component (by solving the proposed linear program).     

On random perturbations of Hamiltonian systems with many degrees of freedom

We consider a class of random perturbations of Hamiltonian systems with many degrees of freedom. We assume that the perturbations consist of two components: a larger one which preserves the energy and destroys all other first integrals, and a smaller one which is a non-degenerate white noise type process. Under these assumptions, we show that the long time behavior of such a perturbed system is described by a diffusion process on a graph corresponding to the Hamiltonian of the system. The graph is homeomorphic to the set of all connected components of the level sets of the Hamiltonian. We calculate the differential operators which govern the process inside the edges of the graph and the gluing conditions at the vertices.     

On the elusiveness of Hamiltonian property

1. IntroductionA gash G is an ordered pair of disjoillt sets (V, E) such that E is a subset of the setof unordered pairs of V, where the sets V and E are finite. The set V is cajled the setof venices and E is called the set of edges. They are usually denoted by V(G) and E(C),respectively. An edge (x, y) is said to join the venices x and y, and is sometimes denotedby xo or ear. By our definition, a graph does not colltain any loOP, neither does it colltainmultiple edges.Other terms undef…     

A successful algorithm for the undirected Hamiltonian path problem

In this paper a polynomial algorithm called the Minram algorithm is presented which finds a Hamiltonian Path in an undirected graph with high frequency of success for graphs up to 1000 nodes. It first reintroduces the concept described in [13] and then explains the algorithm. Computational comparison with the algorithm by Posa [10] is given.It is shown that a Hamiltonian Path is a spanning arborescence with zero ramification index. Given an undirected graph, the Minram algorithm starts by finding a spanning tree which defines a unique spanning arborescence. By suitable pivots it locates a locally minimal value of the ramification index. If this local minima corresponds to zero ramification index then the algorithm is considered to have ended successfully, else a failure is reported.Computational performance of the algorithm on randomly generated Hamiltonian graphs is given. The random graphs used as test problems were generated using the procedure explained in Section 6.1. Comparison with our version of the Posa algorithm which we call Posa-ran algorithm [10] is also made.     

Orientable imbedding of line graphs

In this paper we compute the orientable genus of the line graph of a graph G, when G is a tree and a 2-edge connected graph, all the vertices of which have their degrees equal to 2, 3, 6, or 11 modulo 12, and either G can be imbedded with triangular faces only or G is a bipartite graph which can be imbedded with squares only as faces. In the other cases, we give an upper bound of the genus of line graphs. In this way, we solve the question of the Hamiltonian genus of the complete graph K_n, for every n ≥ 3.     

On due-date based valid cuts for the sequential ordering problem

The Sequential Ordering Problem with precedence relationships was introduced in Escudero (1988), and extended to cover release and due dates in Escudero and Schiomachen (1993). The problem consists of finding a minimum weight Hamiltonian path on a directed graph with weights on the nodes and the arcs, satisfying precedence relationships among the nodes and lower and upper bounds on the Hamiltonian subpaths. In this paper we introduce valid cuts derived from the due date constraints that can be used in a separation framework for the dual (Lagrangian based) relaxation of the problem. We also provide an heuristic separation algorithm to obtain those cuts. This research was supported by DGICYT through grant N. PB95-0407     

Octagonal drawings of plane graphs with prescribed face areas

An orthogonal drawing of a plane graph is called an octagonal drawing if each inner face is drawn as a rectilinear polygon of at most eight (polygonal) vertices and the contour of the outer face is drawn as a rectangle. A slicing graph is obtained from a rectangle by repeatedly slicing it vertically and horizontally. A slicing graph is called a good slicing graph if either the upper subrectangle or the lower one obtained by any horizontal slice will never be vertically sliced, roughly speaking. In this paper we show that every good slicing graph has an octagonal drawing with prescribed face areas, in which the area of each inner face is equal to a prescribed value. Such a drawing has practical applications in VLSI floorplanning. We also give a linear-time algorithm to find such a drawing when a “slicing tree” is given. We furthermore present a sufficient condition for a plane graph to be a good slicing graph.     

Gauss codes,planar hamiltonian graphs,and stack-sortable permutations

In this paper the following three recognition problems are considered: (1) Test whether a given sequence is the Gauss code of a planar self-intersecting curve; (2) test whether a given graph with a known Hamiltonian cycle is planar; and (3) test whether a given permutation can be sorted using two stacks in parallel. These three problems are closely related: A simple linear-time algorithm that solves all three is described. The heart of the algorithm is a data structure, previously used in general planarity testing, called a pile of twin stacks.     

Menus of kuratowski subgraphs

Motivated by heuristic embedding algorithms, this paper is concerned with the organization of potentially large lists of Kuratowski subgraphs of an arbitrary nonpianar graph. A graphical structure called a "nearly Hamiltonian" graph is defined. It is shown that lists of Kuralowski subgraphs can be lexicographically organized in such structures. It is shown that any nonpianar graph contains such structures and at least one such structure with a nonempty list of Kuratowski subgraphs can be located in linear time in ihe edges of the graph.     

On invariant sets in Lagrangian graphs

In this exposition, we show that the Hamiltonian is always constant on a compact invariant connected subset which lies in a Lagrangian graph provided that the Hamiltonian and the graph are sufficiently smooth. We also provide some counterexamples to show that if the Hamiltonian function is not smooth enough, then it may be non-constant on a compact invariant connected subset which lies in a Lagrangian graph.     

The degree sequences of self-complementary graphs

Known necessary conditions for realization of a sequence of integers as the degrees of a self-complementary graph are shown to be sufficient. An algorithm for constructing a realization of such a sequence as degrees of such a graph is illustrated by an example.     

对称群上Cayley图的DNA计算

有一类图称为Cayley图或群图.猜想每个Cayley图都是Hamilton图.求Cayley图和有向Cayley图中的Hamilton圈和路自然产生在计算科学里.这篇文章研究了对称群上Cayley图的DNA计算和给出了求它的Hamilton圈的DNA算法.