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 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.
