The Graph Theory Problem Based On Graph State

Graph theory is a branch of mathematics that deals with graph.The graph in this context is a collection of vertices and a collection of edges that connect pairs of vertices. It has many applications in computer science, engineer, and management. On the other hand, graph state is quantum state, which associate with graph, each edge represent an interaction or entanglement, and each vertice represent qubit. In fact, based on physics, graph states provide a computation model, widely used in quantum entanglement and quantum computer.From graph theory to graph state, it has been studied extensively. In this paper, thinking outside the box, from graph state to graph theory. As we all know, the reconstruction conjecture, says that graphs are determined uniquely by their vertex-deleted graph, up to isomorphism.Here, we provide another problem of graph reconstruction---the LC (local complement) reconstruction, which come from the Pauli y measurement of graph state.In this paper, we define the bipartition sequence and the LC reconstruction. Then, we propose the criterion for the bipartition sequence uniquely identify a graph.On the other hand, we demonstrate, without empty graph and complete graph, any two labelled graphs at least four vertices have the same deck of local complement are uniquely determined. At the same time, we point out the LC reconstruction of the unlabelled graph, and prove the unconnected graph can be LC reconstructible.