Methods Of Researching Graph Properties Based On The Karp Conjecture

It is well known that graph theory has extensive applications in many areas. An important thing concerning to application is to treat graph with computer. Usually, a graph can be installed into a computer by incoding the entries of the triangular part of its adjacency matrix. One problem arising naturally is: Can we detect whether a graph G has some specific property without decoding all the entries of the upper triangular part of its adjacency matrix? That is, given a graph property P on n vertices, must it take n(n-1)/2 queries in the worst case to determine whether a graph G is in P? Karp conjecture is a good answer to it.Karp conjecture: Every nontrivial monotone graph property on n vertices is elusive.Karp conjecture which deals with graph properties is still open and becomes a well-known difficult problem, which associates with graph theory, topology and algebra.The paper is organized as follows:In chapter one, we first review the history and some basic definitions.In chapter two, this work reviews the traditional way of constructing Boolean functions, and propose a new method to construct Boolean function. Through comparing the two methods by calculating a Boolean function, we show the strengths and weakness of the two methods.In chapter three, this work reviews the three main methods and a method which is not often used in studying the Karp conjecture and gives proofs of some theories and elusiveness of some graph properties, for instance, the elusiveness of connectedness. We also propose four new corollaries.In chapter four, this work propose a new method, that is, the complexity methods, to overcome the drawback of existing methods, which are focus on only one kind of graph property. This new method could determine the elusiveness of the whole group of graph properties just by deceting some characters of one graph property in it.