▎ 摘　　要

Based on the characteristics of graphene, this paper designs a method to solve the Minimum Vertex Covering problem of a graph. We designed a DNA-graphene oxide reaction platform in advance. At the same time, we designed the single DNA strands corresponding to each edge, and used the single DNA strands of edges associated with each vertex to represent the vertex; then, the single DNA strands of edges representing the combination of vertices was added into the DNA-graphene oxide reaction platform, and the change of fluorescence signal was detected. According to the change of fluorescence signal, whether a combination of vertices is the vertex cover of a graph or not can be determined. Our method takes advantage of the excellent properties of graphene, which can reduce the complexity of solving the Minimum Vertex Covering problem of a graph. At the same time, the combination of DNA computing and Nanotechnology provides a new research idea for the future research of DNA computing.