Some recent results in hamiltonian graphs

A variety of recent developments in hamiltonian theory are reviewed. In particular, several sufficient conditions for a graph to be hamiltonian, certain hamiltonian properties of line graphs, and various hamiltonian properties of powers of graphs are discussed. Furthermore, the concept of an n-distant hamiltonian graph is introduced and several theorems involving this special class of hamiltonian graphs are presented.     

Bipartite graphs with every matching in a cycle

We give sufficient Ore-type conditions for a balanced bipartite graph to contain every matching in a hamiltonian cycle or a cycle not necessarily hamiltonian. Moreover, for the hamiltonian case we prove that the condition is almost best possible.     

On Super Hamiltonian Semigroups

The concept of super hamiltonian semigroup is introduced. As a result, the structure theorems obtained by A. Cherubini and A. Varisco on quasi commutative semi-groups and quasi hamiltonian semigroups respectively are extended to super hamiltonian semigroups.     

Chromatic properties of hamiltonian graphs

We study the problem of the location of real zeros of chromatic polynomials for some families of graphs. In particular, a problem presented by Thomassen (see [On the number of hamiltonian cycles in bipartite graphs, Combin. Probab. Comput. 5 (1996) 437–442.]) is discussed and a result for hamiltonian graphs is presented. An open problem is stated for 2-connected graphs with a hamiltonian path.     

On local characterizations of Hamiltonian tournaments

We characterize the hamiltonian tournaments that admits exactly one spanning cycle and the hamiltonian tournaments with the least number of 3-cycles by their hamiltonian subtournaments which have the same properties respectively.     

Hamilton cycles in prisms

The prism over a graph G is the Cartesian product G □ K₂ of G with the complete graph K₂. If G is hamiltonian, then G□K₂ is also hamiltonian but the converse does not hold in general. Having a hamiltonian prism is shown to be an interesting relaxation of being hamiltonian. In this article, we examine classical problems on hamiltonicity of graphs in the context of having a hamiltonian prism. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 249–269, 2007     

Schrijver图SG(2k+2,k)的Hamilton性

通过图G的每个顶点的路称为Hamilton路,通过图G的每个顶点的圈称为Hamilton圈,具有Hamilton圈的图G称为Hamilton图.1952年Dirac曾得到关于Hamilton图一个充分条件的结论:图G有n个顶点,如果每个顶点υ满足:d(υ)≥n/2,则图G是Hamilton图.本文研究了Schrijver图SG(2k+2,k)的Hamilton性,采用寻找Hamilton圈的方法得出了Schrijver图SG(2k+2,k)是Hamilton图.     

Hille-Yosida定理在一类无穷维Hamiltion系统中的应用

应用Hille-Yosida定理研究了无穷维Hamilton算子,得到了一个无穷维Hamilton系统初值问题解的存在性定理,并把结果应用在由一类双曲型偏微分方程导出的无穷维Hamilton系统中,给出了此类无穷维Hamilton系统解的存在性定理.     

Hamiltonian cycles in cayley color graphs

A group Γ is said to possess a hamiltonian generating set if there exists a minimal generating set Δ for Γ such that the Cayley color graph D_Δ(Γ) is hamiltonian. It is shown that every finite abelian group has a hamiltonian generating set. Certain classes of nonabelian groups are also investigated.     

Hamiltonian decompositions of products of cycles

A graph is said to be decomposable into hamiltonian cycles if its edge set can be partitioned into hamiltonian cycles. We show that the cartesian product of any three cycles can be decomposed into three hamiltonian cycles, thus settling a conjecture by Kotzig. We also show that, more generally, the cartesian product of 2^a3^b graphs, each decomposable into m hamiltonian cycles, can be decomposed into 2^a3^bm hamiltonian cycles.     

Hamiltonian index is NP-complete

In this paper we show that the problem to decide whether the hamiltonian index of a given graph is less than or equal to a given constant is NP-complete (although this was conjectured to be polynomial). Consequently, the corresponding problem to determine the hamiltonian index of a given graph is NP-hard. Finally, we show that some known upper and lower bounds on the hamiltonian index can be computed in polynomial time.     

On 2-factor hamiltonian regular bipartite graphs

A k-regular bipartite graph is said to be 2-factor hamiltonian if each of its 2-factor is hamiltonian. It is well known that if a k-regular bipartite graph is 2-factor hamiltonian, then k?Q3. In this paper, we give a new proof of this fact.     

Hamilton cycles in 6-connected claw-free graphs (Extended abstract)

Thomassen conjectured in 1986 that every 4-connected line graph is hamiltonian. In this paper, we show that 6-connected line graphs are hamiltonian, improving on an analogous result for 7-connected line graphs due to Zhan in 1991. Our result implies that every 6-connected claw-free graph is hamiltonian.     

Old Hamiltonian Ideas from a New Point of View

We prove a sufficient condition for graphs to be hamiltonian. This result generalizes five sufficient conditions for hamiltonian graphs and is non-comparable with many well-known ones.     

Hamiltonian cycles through prescribed edges of 4-connected maximal planar graphs

In 1956, W.T. Tutte proved that every 4-connected planar graph is hamiltonian. Moreover, in 1997, D.P. Sanders extended this to the result that a 4-connected planar graph contains a hamiltonian cycle through any two of its edges. It is shown that Sanders’ result is best possible by constructing 4-connected maximal planar graphs with three edges a large distance apart such that any hamiltonian cycle misses one of them. If the maximal planar graph is 5-connected then such a construction is impossible.     

On local characterizations of Hamiltonian tournaments

We characterize the hamiltonian tournaments that admits exactly one spanning cycle and the hamiltonian tournaments with the least number of 3-cycles by their hamiltonian subtournaments which have the same properties respectively. AMS(MOS) Subject Classification (1980)-05C20. Work performed under the auspices of the Gruppo Nazionale di Topologia (Fondi MURST 40%). This paper is in its final form and no version of it will be submitted for publication elsewhere     

Almost all Cayley graphs are hamiltonian

It has been conjectured that there is a hamiltonian cycle in every finite connected Cayley graph. In spite of the difficulty in proving this conjecture, we show that almost all Cayley graphs are hamiltonian. That is, as the order n of a groupG approaches infinity, the ratio of the number of hamiltonian Cayley graphs ofG to the total number of Cayley graphs ofG approaches 1.Supported by the National Natural Science Foundation of China, Xinjiang Educational Committee and Xinjiang University.     

Independent Production of Non Hamiltonian Graphs

The decision whether a graph is hamiltonian or not is known to be an NP-complete problem. The importance of this kind of problem motivate several researchers in heuristics development. However, problems arise in the evaluating of this heuristics, more often because it is difficult to produce independent data. In this paper we develop methods to produce non hamiltonian graphs, based on independence subsets and toughness arguments. We also present a family of non hamiltonian graphs with strong restrictions, that is, planar 1-tough non hamiltonan graphs with no separation triangles.     

A canonical representation of trivalent hamiltonian graphs

A canonical representation of trivalent hamiltonian graphs in the form of “span lists” had been proposed by J. Lederberg. It is here presented in a modified form due to H. S. M. Coxeter and the author, and therefore called “LCF notation.” This notation has the advantage of being more concise than Lederberg's original span lists whenever the graph has a hamiltonian circuit with rotational symmetry. It is also useful as a method for a systematic classification of trivalent hamiltonian graphs and allows one to define for such graphs two interesting properties, called, respectively, “antipalindromic” and “quasiantipalindromic.”.