Abstract: The integrity of a graph is mainly studied and some results on the integrity are given. Given the number of vertices and the number of edges in a class of graphs, the problem of how to determine a graph that has the minimum integrity among the class is studied. Also, if the number of vertices and the integrity in a class of graphs are fixed, the problem of how to determine a graph that has the maximum number of edges among them is investigated. For the optimal designs of the minimal integrity, the theoretics and methods are provided.

Key words: Graph theory, Integrity, Minimum integrity