On Connected 2-K n -Residual Graphs

A graph G is said to be K _n -residual if for every point u in G, the graph obtained by removing the closed neighborhood of u from G is isomorphic to K _n . We inductively define a multiply-K _n -residual graph by saying that G is m-K _n -residual if the removal of the closed neighborhood of any vertex of G results in an (m – 1)-K _n -residual graphs. Erdös, Harary and Klawe 2] determined the minimum order of the m?K _n -residual graphs for all m and n, which are not necessarily connected, the minimum order of connected; K _n -residual graphs, all K _n -residual extremal graphs. They also stated some conjectures regarding the connected case. In this paper, we determine the minimum order of a connected 2-K _n -residual graph and specify the extremal graphs, expect for n = 3. In particular, we determining only one connected 2-K ₄-residual graph of minimal order, and show that there is a connected 2-K ₆-residual graph non isomorphic to K ₈ × K ₃ with minimum order. Finally we present and a revised version of the conjecture in 2].