Let G be a 2 connected simple graph of order n and connectivity k .Bauer, Broersma and Li proved that for an independent set S=u,v,w, d(u)+d(v)+d(w)≥n+k ,then G is Hamiltonian. This paper improves ...Let G be a 2 connected simple graph of order n and connectivity k .Bauer, Broersma and Li proved that for an independent set S=u,v,w, d(u)+d(v)+d(w)≥n+k ,then G is Hamiltonian. This paper improves the result.Let S be an independent set. If there exist u,v∈S,du,v=2, then S is called a 2 independent set. This paper proves the following result. Let G be a simple graph of order n and connectivity k≥2 . If for every 2 independent set S=u,v,w, d(u)+d(v)+d(w)≥n+k , then G is Hamiltonian. This result implies that we may consider all triples of 2 independent set instead of all triples of independent set.展开更多
DNA computing is a novel method for solving a class of intractable computational problem, in which the computing can grow exponentially with problem size. Up to now, many accomplishments have been achieved to improve ...DNA computing is a novel method for solving a class of intractable computational problem, in which the computing can grow exponentially with problem size. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability. Hamilton Graph Problem has been solved by means of molecular biology techniques. A small graph was encoded in molecules of DNA, and the 'operations' of the computation were performed with standard protocols and enzymes. This work represents further evidence for the ability of DNA computing to solve NP-complete search problems.展开更多
Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u.For any UV(G),let N(U)=∪_~u∈U N(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgra...Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u.For any UV(G),let N(U)=∪_~u∈U N(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgraph isomorphic to K_~1,3 .One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng,et al.: Let G be a 2-connected claw-free graph of order n,and d(u)+d(v)+d(w)≥n-2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that,for any three positive integers s,t and w,such that if G is a (s+t+w-1)-connected claw-free graph of order n,and d(S)+d(T)+d(W)>n-(s+t+w) for every three disjoint independent vertex sets S,T,W with |S|=s,|T|=t,|W|=w,and S∪T∪W is also independent,then G is Hamiltonian.Other related results are obtained too.展开更多
文摘Let G be a 2 connected simple graph of order n and connectivity k .Bauer, Broersma and Li proved that for an independent set S=u,v,w, d(u)+d(v)+d(w)≥n+k ,then G is Hamiltonian. This paper improves the result.Let S be an independent set. If there exist u,v∈S,du,v=2, then S is called a 2 independent set. This paper proves the following result. Let G be a simple graph of order n and connectivity k≥2 . If for every 2 independent set S=u,v,w, d(u)+d(v)+d(w)≥n+k , then G is Hamiltonian. This result implies that we may consider all triples of 2 independent set instead of all triples of independent set.
基金Supported by the CNSF(60274026 60174047+1 种基金 30370356) Supported by the Anhui Provinc'e Educational Committee Foundation(2003Kj098)
文摘DNA computing is a novel method for solving a class of intractable computational problem, in which the computing can grow exponentially with problem size. Up to now, many accomplishments have been achieved to improve its performance and increase its reliability. Hamilton Graph Problem has been solved by means of molecular biology techniques. A small graph was encoded in molecules of DNA, and the 'operations' of the computation were performed with standard protocols and enzymes. This work represents further evidence for the ability of DNA computing to solve NP-complete search problems.
文摘Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u.For any UV(G),let N(U)=∪_~u∈U N(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgraph isomorphic to K_~1,3 .One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng,et al.: Let G be a 2-connected claw-free graph of order n,and d(u)+d(v)+d(w)≥n-2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that,for any three positive integers s,t and w,such that if G is a (s+t+w-1)-connected claw-free graph of order n,and d(S)+d(T)+d(W)>n-(s+t+w) for every three disjoint independent vertex sets S,T,W with |S|=s,|T|=t,|W|=w,and S∪T∪W is also independent,then G is Hamiltonian.Other related results are obtained too.
