On Connected m-HPK -Residual Graphs

We define m-HPK -residual graphs in which HPK is a hyperplane complete graph. We extend P. Erd？s, F. Harary, and M. Klawe's definition of plane complete residual graph to hyperplane and obtain the hyperplane complete residual graph. Further, we obtain the minimum order of HPK -residual graphs and m-HPK -residual graphs. In addition, we obtain a unique minimal HPK -residual graphs and a unique minimal m-HPK -residual graphs. 1. Introduction A graph is said to be -residual graph [1], if for every vertex in , the graph obtained from by removing the closed neighborhood of is isomorphic [2–6] to . We inductively define a multiply -residual graph by saying that is -residual graph, if the removal of the closed neighborhood of any vertex of results in an -residual graph, where of course a -residual graph is simply said to be -residual graph. It is natural to ask what is the minimum number of vertices that an -residual graph must contain? It is easy to prove that this number is and that the only -residual graph with this number of vertex is . In [1], Erd？s et al. show that a connected -residual graph must have at least points, if . Furthermore, the Cartesian product is the only such graph with points for . They complete the result by determining all connected -residual graphs of minimal order for . In [1], the following conjectures were stated. Conjecture 1 (see [1]). If , then every connected -residual graph has at least vertices. Conjecture 2 (see [1]). For large, there is a unique smallest connected -residual graph. Theorem 3 (see [1]). (1) If is an -residual graph, then for any vertex in G, the degree . (2) Every -residual graph has at least vertices, and is the only -residual graph with vertices. (3) Every connected -residual graph has at least vertices, if . (4) If , then is a connected -residual graph of minimum order, and, except for and , it is the only such graph. We know that these supporting results are summarized in residual graph [7–16]. In this paper, we will study the important properties of hyperplane complete graph in relain to the minimum order of hyperplane complete graph and the minimum graph of hyperplane complete graph. We will investigate Erd？s, Harary, and Klawe’s residual graph and obtain the minimum order of -residual graphs and - -residual graphs. And we also show a unique minimal connected -residual graphs of order and a unique minimal connected - -residual graphs of order . In general, we follow the notation in [1]. In particular, is the number of vertices in a graph , is the closed neighborhood of the vertex , and are called as