Erd s Conjecture on Connected Residual Graphs

A graph G is said to be F-residual if for every point u in G, the graph obtained by removing the closed neighborhood of u from G is isomorphic to F. Similarly, if the remove of m consecutive closed neighborhoods yields Kn, then G is called m-Kn-residual graph. Erd s determine the minimum order of the m-Kn-residual graph for all m and n, the minimum order of the connected Kn-residual graph is found and all the extremal graphs are specified. Jiangdong Liao and Shihui Yang determine the minimum order of the connected 2-Kn-residual graph is found and all the extremal graphs are specified expected for n=3, and in this paper, we prove that the minimum order of the connected 3-Kn-residual graph is found and all the extremal graphs are specified expected for n=5, 7, 9,10, and we revised Erd s conjecture.