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.展开更多
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.展开更多
[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,respectivel...[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.展开更多
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.
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.展开更多
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.展开更多
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.展开更多
We prove that if G is a graph of order n and connectivity k,and thereexists some t,t（?）k,such that for every independent set S={x<sub>0</sub>,x<sub>1</sub>,…x<sub>t</sub>} ofcard...We prove that if G is a graph of order n and connectivity k,and thereexists some t,t（?）k,such that for every independent set S={x<sub>0</sub>,x<sub>1</sub>,…x<sub>t</sub>} ofcardinality t+1,we havesum from i=0 to t |N(S/{x<sub>i</sub>}|】t（n-1）,then G is Hamiltonian.展开更多
Let G be a graph of order n. For graph to be Hamiltonian, beginning with Dirac's classic result in 1952, Dirac's theorem was followed by that of Ore in 1960. In 1984, Fan generalized Dirac's theorem and Or...Let G be a graph of order n. For graph to be Hamiltonian, beginning with Dirac's classic result in 1952, Dirac's theorem was followed by that of Ore in 1960. In 1984, Fan generalized Dirac's theorem and Ore's theorem as if G is a 2-connected graph of order n and max {d (u),d (v)}≥n/2 for each pair of vertices u and v with d (u,v)=2, then G is hamiltonian. In 1991, Faudree et al proved that if G is a 2-connected graph and, |N (u)∪N (v)|+δ(G)≥n for each pair of nonadjacent vertices u,v∈V(G), then G is hamiltonian. This paper generalizes the above conditions of Dirac, Ore, Fan and Faudree et al in the case of 3-connected graph and proves that if G is a 3-connected graph of order n and max{|N(x)∪ N (y)| +d (u), |N (w)∪N (z)|+d (v)}≥n for every choice of 6 Essential independent vertices, then G is hamiltonian.展开更多
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.展开更多
A graph G has the hourglass property if every induced hourglass S（a tree with a degree sequence 22224） contains two non-adjacent vertices which have a common neighbor in G-V（S）.For an integer k≥4,a graph G has th...A graph G has the hourglass property if every induced hourglass S（a tree with a degree sequence 22224） contains two non-adjacent vertices which have a common neighbor in G-V（S）.For an integer k≥4,a graph G has the single k-cycle property if every edge of G,which does not lie in a triangle,lies in a cycle C of order at most k such that C has at least「｜V（C） /2」 edges which do not lie in a triangle,and they are not adjacent.In this paper,we show that every hourglass-free claw-free graph G of δ（G） ≥3 with the single 7-cycle property is Hamiltonian and is best possible;we also show that every claw-free graph G of δ（G） ≥3 with the hourglass property and with single 6-cycle property is Hamiltonian.展开更多
The line graph for the complement of the zero divisor graph for the ring of Gaussian integers modulo n is studied. The diameter, the radius and degree of each vertex are determined. Complete characterization of Hamilt...The line graph for the complement of the zero divisor graph for the ring of Gaussian integers modulo n is studied. The diameter, the radius and degree of each vertex are determined. Complete characterization of Hamiltonian, Eulerian, planer, regular, locally and locally connected is given. The chromatic number when is a power of a prime is computed. Further properties for and are also discussed.展开更多
基金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 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.
文摘[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.
文摘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.
基金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.
基金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.
文摘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.
基金Project supported by National Natural Science Foundation of China
文摘We prove that if G is a graph of order n and connectivity k,and thereexists some t,t（?）k,such that for every independent set S={x<sub>0</sub>,x<sub>1</sub>,…x<sub>t</sub>} ofcardinality t+1,we havesum from i=0 to t |N(S/{x<sub>i</sub>}|】t（n-1）,then G is Hamiltonian.
基金Research supported by NSF of Hainan (No.10501) NSF of the Education Departmant of Hainan(No.Hjkj 200529)
文摘Let G be a graph of order n. For graph to be Hamiltonian, beginning with Dirac's classic result in 1952, Dirac's theorem was followed by that of Ore in 1960. In 1984, Fan generalized Dirac's theorem and Ore's theorem as if G is a 2-connected graph of order n and max {d (u),d (v)}≥n/2 for each pair of vertices u and v with d (u,v)=2, then G is hamiltonian. In 1991, Faudree et al proved that if G is a 2-connected graph and, |N (u)∪N (v)|+δ(G)≥n for each pair of nonadjacent vertices u,v∈V(G), then G is hamiltonian. This paper generalizes the above conditions of Dirac, Ore, Fan and Faudree et al in the case of 3-connected graph and proves that if G is a 3-connected graph of order n and max{|N(x)∪ N (y)| +d (u), |N (w)∪N (z)|+d (v)}≥n for every choice of 6 Essential independent vertices, then G is hamiltonian.
文摘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(11071016 and 11171129)the Beijing Natural Science Foundation(1102015)
文摘A graph G has the hourglass property if every induced hourglass S（a tree with a degree sequence 22224） contains two non-adjacent vertices which have a common neighbor in G-V（S）.For an integer k≥4,a graph G has the single k-cycle property if every edge of G,which does not lie in a triangle,lies in a cycle C of order at most k such that C has at least「｜V（C） /2」 edges which do not lie in a triangle,and they are not adjacent.In this paper,we show that every hourglass-free claw-free graph G of δ（G） ≥3 with the single 7-cycle property is Hamiltonian and is best possible;we also show that every claw-free graph G of δ（G） ≥3 with the hourglass property and with single 6-cycle property is Hamiltonian.
文摘The line graph for the complement of the zero divisor graph for the ring of Gaussian integers modulo n is studied. The diameter, the radius and degree of each vertex are determined. Complete characterization of Hamiltonian, Eulerian, planer, regular, locally and locally connected is given. The chromatic number when is a power of a prime is computed. Further properties for and are also discussed.
