DNA computing is a novel method for solving a class of intractable computationalproblems in which the computing can grow exponentially with problem size. Up to now, manyaccomplishments have been achieved to improve it...DNA computing is a novel method for solving a class of intractable computationalproblems in which the computing can grow exponentially with problem size. Up to now, manyaccomplishments have been achieved to improve its performance and increase its reliability.Hamilton Graph Problem has been solved by means of molecular biology techniques. A smallgraph was encoded in molecules of DNA, and the “operations” of the computation wereperformed with standard protocols and enzymes. This work represents further evidence forthe 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.展开更多
Joseph B.Klerlein 在文[1]中证明了有限 Abell 群Γ具有极小生成元集△使Cayley 色图 D_△(T)为有向 Hamilton 图.本文证明了当Γ是 Abell 群时,连通的cayley 色图D_△(Γ)具有有向 Hamilton 路对任意的△成立,并举例说明一般的D_△(Γ...Joseph B.Klerlein 在文[1]中证明了有限 Abell 群Γ具有极小生成元集△使Cayley 色图 D_△(T)为有向 Hamilton 图.本文证明了当Γ是 Abell 群时,连通的cayley 色图D_△(Γ)具有有向 Hamilton 路对任意的△成立,并举例说明一般的D_△(Γ)未必是 Hamilton 图.展开更多
基金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 computationalproblems in which the computing can grow exponentially with problem size. Up to now, manyaccomplishments have been achieved to improve its performance and increase its reliability.Hamilton Graph Problem has been solved by means of molecular biology techniques. A smallgraph was encoded in molecules of DNA, and the “operations” of the computation wereperformed with standard protocols and enzymes. This work represents further evidence forthe 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.
