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 Hamiltonia...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.展开更多
For a vertex set{u<sub>1</sub>,u<sub>2</sub>,…,u<sub>k</sub>}of a graph G with n vertices,let s(G;{u<sub>1</sub>,u<sub>2</sub>,…,u<sub>k</sub>...For a vertex set{u<sub>1</sub>,u<sub>2</sub>,…,u<sub>k</sub>}of a graph G with n vertices,let s(G;{u<sub>1</sub>,u<sub>2</sub>,…,u<sub>k</sub>})=Σ<sub>1</sub>≤i≤j≤k<sup>|N(u<sub>i</sub>)UN(u<sub>j</sub>)|</sup>, NC<sub>k</sub>.=min{s(G;{x<sub>1</sub>,…,x<sub>k</sub>}):{x<sub>1</sub>,…,x<sub>k</sub>}is an independent set}. In this paper,we shall prove that if G is 3-connected and NC<sub>4</sub>≥3n,then G is either a hamiltonian or Petersen graph.This generalizes some results on the neighborhood union conditions for hamiltonian graphs.展开更多
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 ...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 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 ...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 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....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.展开更多
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...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.展开更多
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 g...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.展开更多
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 ev...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.展开更多
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...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.展开更多
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 ...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.展开更多
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 ...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.展开更多
基金Project supported by National Natural Foundation of China
文摘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.
基金Supported by the National Natural Science Foundation of ChinaSupported also by the Post-doctoral Foundation of China
文摘For a vertex set{u<sub>1</sub>,u<sub>2</sub>,…,u<sub>k</sub>}of a graph G with n vertices,let s(G;{u<sub>1</sub>,u<sub>2</sub>,…,u<sub>k</sub>})=Σ<sub>1</sub>≤i≤j≤k<sup>|N(u<sub>i</sub>)UN(u<sub>j</sub>)|</sup>, NC<sub>k</sub>.=min{s(G;{x<sub>1</sub>,…,x<sub>k</sub>}):{x<sub>1</sub>,…,x<sub>k</sub>}is an independent set}. In this paper,we shall prove that if G is 3-connected and NC<sub>4</sub>≥3n,then G is either a hamiltonian or Petersen graph.This generalizes some results on the neighborhood union conditions for hamiltonian graphs.
基金Supported by the National Natural Science Foundation ofChina (No. 196 710 5 0 )
文摘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 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 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.
基金Supported by the National Natural Science Foundation of China under Grant No.11101383,11271338 and 11201432
文摘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.
基金the National Natural Science Foundationof China (No.196 710 5 0 )
文摘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.
基金Supported by National Natural Science Foundation of China(Grant No.12071442)the Fundamental Research Funds for the Central Universities under(Grant No.020314380035)。
文摘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.
基金Supported by NSFC(Grant Nos.11271300 and 11571135)the project NEXLIZ–CZ.1.07/2.3.00/30.0038+1 种基金the project P202/12/G061 of the Czech Science Foundation and by the European Regional Development Fund(ERDF)the project NTIS-New Technologies for Information Society,European Centre of Excellence,CZ.1.05/1.1.00/02.0090
文摘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.
基金Supported by NSFC(Grant No.11271300)the Natural Science Foundation of Shaanxi Province(Grant No.2016JQ1002)the Project NEXLIZ–CZ.1.07/2.3.00/30.0038
文摘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.
文摘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.