%0 Journal Article
%T Erd s Conjecture on Connected Residual Graphs
%A Jiangdong Liao
%A Gonglun Long
%A Mingyong Li
%J Journal of Computers
%D 2012
%I Academy Publisher
%R 10.4304/jcp.7.6.1497-1502
%X 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.
%K Residual-graph
%K Closed neighborhood
%K Adjacent
%K Cartesian product
%U http://ojs.academypublisher.com/index.php/jcp/article/view/5619