ON THE CONSTRUCTION AND ENUMERATION OF HAMILTONIAN GRAPHS

In this paper we give a formula for enumerating the equivalent classes of orderly labeled Hamiltonian graphs under group D. and two algorithms for constructing these equivalent classes and all nonisomorphic Hamiltonian graphs. Some computational results obtained by microcomputers are listed.

A New Neighborhood Union Condition for Hamiltonian Graphs

For a vertex set{u1,u2,…,uk}of a graph G with n vertices,let s（G;{u1,u2,…,uk}）=Σ1≤i≤j≤k|N（ui）UN（uj）|, NCk.=min{s（G;{x1,…,xk}）:{x1,…,xk}is an independent set}. In this paper,we shall prove that if G is 3-connected and NC4≥3n,then G is either a hamiltonian or Petersen graph.This generalizes some results on the neighborhood union conditions for hamiltonian graphs.

Sufficient Condition for Hamiltonian Graphs Concerning Degree and Neighborhood Union

Let G be a graph of order n. G is called Hamiltonian if G has a spanning cycle. Denote N(v)={u∈V(G)｜uv∈E(G)}. Then by considering the degree and neighborhood union conditions of G, the paper gives a generalization of two theorems of Benhocine et al and Faudree et al. Let G be a 2\|connected graph of order n and α≤n2.If max{d(u),d(v)}≥n-12 or |N(u)∪N(v)|≥n-δ for every pair vertices u and v with d(u,v)= 2,then G is Hamiltonian with some exceptions.

Two Sufficient Conditions for Hamiltonian Graphs

Two venices of a graph are said to be c-pair if the distance between them equals to 2 and the degrees of them are both less than helf the number of the venices of the graph. This paper gives two sufficient conditions for a 3-connected or 1-tough graph to be Hamiltonian.The conditions are the generalization of the Fan-conditions in the sense that the c-pair is allowed here,but is not allowed in the Fan-conditions.

Genome Sequencing Using Graph Theory Approach

Genome sequencing is the process of determining in which order the nitrogenous bases also known as nucleotides within a DNA molecule are arranged. Every organism’s genome consists of a unique sequence of nucleotides. These nucleotides bases provide the phenotypes and genotypes of a cell. In mathematics, Graph theory is the study of mathematical objects known as graphs which are made of vertices (or nodes) connected by either directed edges or indirect edges. Determining the sequence in which these nucleotides are bonded can help scientists and researchers to compare DNA between organisms, which can help show how the organisms are related. In this research, we study how graph theory plays a vital part in genome sequencing and different types of graphs used during DNA sequencing. We are going to propose several ways graph theory is used to sequence the genome. We are as well, going to explore how the graphs like Hamiltonian graph, Euler graph, and de Bruijn graphs are used to sequence the genome and advantages and disadvantages associated with each graph.

A Characterization of PM-compact Hamiltonian Bipartite Graphs

The perfect matching polytope of a graph G is the convex hull of the incidence vectors of all perfect matchings in G. A graph is called perfect matching compact（shortly, PM-compact）, if its perfect matching polytope has diameter one. This paper gives a complete characterization of simple PM-compact Hamiltonian bipartite graphs. We first define two families of graphs, called the H2C-bipartite graphs and the H23-bipartite graphs, respectively. Then we show that, for a simple Hamiltonian bipartite graph G with ｜V（G）｜ ≥ 6, G is PM-compact if and only if G is K3,3, or G is a spanning Hamiltonian subgraph of either an H2C-bipartite graph or an H23-bipartite graph.

Spectral Radius of Hamiltonian Planar Graphs and Outerplanar Graphs

The spectral radius is an important parameter of a graph related to networks. A method for estimating the spectral radius of each spanning subgraph is used to prove that the spectral radius of a Hamiltonian planar graph of order n≥4 is less than or equal to 2+3n-11 and the spectral radius of the outerplanar graph of order n≥6 is less than or equal to 22+n-5, which are improvements over previous results. A direction for further study is then suggested.

关于3-正则哈密尔顿图的围长的一个注记

It is well-known that the Petersen graph is nonhamiltonian.A very short proof for this result was presented in[2]due to D.B.West.In this note,by extending the proof technique in[2],we briefly show that the girth of every 3-regular hamiltonian graph on n≥10 vertices is at most(n+4)/3.

Induced Subgraphs with Large Degrees at End-vertices for Hamiltonicity of Claw-free Graphs

A graph is called claw-free if it contains no induced subgrapn lsomorpmc to K1,3. Matthews and Sumner proved that a 2-connected claw-free graph G is Hamiltonian if every vertex of it has degree at least （[V（G）I - 2）/3. At the workshop CSzC （Novy Smokovec, 1993）, Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies of N （the graph obtained from a triangle by adding three disjoint pendant edges）. Fujisawa and Yamashita showed that the degree condition of Matthews and Sumner can be restricted only to end-vertices of induced copies of Z1 （the graph obtained from a triangle by adding one pendant edge）. Our main result in this paper is a characterization of all graphs H such that a 2-connected claw-free graph G is Hamiltonian if eachend-vertex of every induced copy of H in G has degree at least IV（G）I/3 ＋ 1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.end-vertex of every induced copy of H in G has degree at least IV（G）I/3 ＋ 1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.

Degree Conditions Restricted to Induced Paths for Hamiltonicity of Claw-heavy Graphs

Broersma and Veldman proved that every 2-connected claw-free and P6-free graph is hamil- tonian. Chen et al. extended this result by proving every 2-connected claw-heavy and P6-free graph is hamiltonian. On the other hand, Li et al. constructed a class of 2-connected graphs which are claw-heavy and P6-o-heavy but not hamiltonian. In this paper, we further give some Ore-type degree conditions restricting to induced copies of P6 of a 2-connected claw-heavy graph that can guarantee the graph to be hamiltonian. This improves some previous related results.

ON A CONJECTURE CONCERNING k-HAMILTON-NICE SEQUENCES

In this paper, we prove that a non-negative rational number sequence (a1,a2,... ,ak+1) is k-Hamilton-nice, if (1) and (2) implies for arbitrary i1,i2,...,i h∈{1,2,... ,k}. This result was conjectured by Guantao Chen and R.H. Schelp, and it generalizes several well-known sufficient conditions for graphs to be Hamiltonian.