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.

An Upper Bound on the A_(α)-spectral Radius of Hamiltonian Graphs with Given Size

[App1.Anal.Discrete Math.,2017,11(1):81-107] defined the A_α-matrix of a graph G as A_α(G)=αD(G)+(1-α)A(G),where α∈[0,1],D(G) and A(G) are the diagonal matrix of degrees and the adjacency matrix of G,respectively.The largest eigenvalue of A_α(G)is called the A_α-spectral radius of G,denoted by ρ_α(G).In this paper,we give an upper bound on ρ_α(G) of a Hamiltonian graph G with m edges for α∈[1/2,1),and completely characterize the corresponding extremal graph in the case when m is odd.In order to complete the proof of the main result,we give a sharp upper bound on the ρ_α(G) of a connected graph G in terms of its degree sequence.

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.

A Cycle Theorem for Hamiltonian Graphs without K 1,3 *

Let G=(V, E) be a hamiltonian K 1.3 free graph such that d(x) |V| 2 and G is connected for some vertex x of G . Then G is pancyclic with a few number of exceptions.

A Localization of Dirac's Theorem for Hamiltonian Graphs

New sufficient conditions for Hamiltonian graphs are obtainedin this paper, which generalize Fan's theorem and Bedrossian et al's result .

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.

A Note on the Girth of 3-Regular Hamiltonian Graph

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.

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.

Every 3-connected {K_(1,3),N_(3,3,3)}-free graph is Hamiltonian

For non-negative integers i,j and k,let N i,j,k be the graph obtained by identifying end vertices of three disjoint paths of lengths i,j and k to the vertices of a triangle.In this paper,we prove that every 3-connected {K1,3,N3,3,3 }-free graph is Hamiltonian.This result is sharp in the sense that for any integer i>3,there exist infinitely many 3-connected {K1,3,Ni,3,3 }-free non-Hamiltonian graphs.

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.