# On Connectedm-HPK(n1,n2,n3,n4)[Kt]-Residual Graphs

Authors: Huiming Duan; Yonghong Li
Journal: Journal of Discrete Mathematics
 (2013)

---

## Abstract

We definem-HPK(n1,n2,n3,n4)[Kt]-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(n1,n2,n3,n4)[Kt]-residual graphs and m-HPK(n1,n2,n3,n4)[Kt]-residual graphs. In addition, we obtain a unique minimal HPK(n1,n2,n3,n4)[Kt]-residual graphs and a unique minimal m-HPK(n1,n2,n3,n4)[Kt]-residual graphs.


---

## Body

## 1. Introduction

A graphG is said to be F-residual graph [1], if for every vertex v in G, the graph obtained from G by removing the closed neighborhood of v is isomorphic [2–6] to F. We inductively define a multiply F-residual graph by saying that G is m-F-residual graph, if the removal of the closed neighborhood of any vertex of G results in an (m-1)-F-residual graph, where of course a 1-F-residual graph is simply said to be F-residual graph.It is natural to ask what is the minimum number of vertices that anm-Kn-residual graph must contain? It is easy to prove that this number is (m+1)n and that the only m-Kn-residual graph with this number of vertex is (m+1)Kn. In [1], Erdös et al. show that a connected Kn-residual graph must have at least 2(n+1) points, if n≠2. Furthermore, the Cartesian product G≅Kn+1×K2 is the only such graph with 2(n+1) points for n≠2,3,4. They complete the result by determining all connected Kn-residual graphs of minimal order for n=2,3,4.In [1], the following conjectures were stated.Conjecture 1 (see [1]).
Ifn≠2, then every connected m-Kn-residual graph has at least min{2n(m+1),(n+m)(m+1)} vertices.Conjecture 2 (see [1]).
Forn large, there is a unique smallest connected m-Kn-residual graph.Theorem 3 (see [1]).
(1) IfG is an F-residual graph, then for any vertex u in G, the degree d(u)=v(G)-v(F)-1.
(2) Everym-Kn-residual graph has at least (m+1)n vertices, and (m+1)Kn is the only m-Kn-residual graph with (m+1)n vertices.
(3) Every connectedKn-residual graph has at least 2n+2 vertices, if n≠2.
(4) Ifn≠2, then G≅Kn+1×K2 is a connected Kn-residual graph of minimum order, and, except for n=3 and n=4, 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 HPK(n1,n2,n3,n4)[Kt]-residual graphs and m-HPK(n1,n2,n3,n4)[Kt]-residual graphs. And we also show a unique minimal connected HPK(n1,n2,n3,n4)[Kt]-residual graphs of order (n1+1)(n2+1)(n3+1)(n4+1)t and a unique minimal connected m-HPK(n1,n2,n3,n4)[Kt]-residual graphs of order (n1+m)(n2+m)(n3+m)(n4+m)t.In general, we follow the notation in [1]. In particular, v(G) is the number of vertices in a graph G, N(u) is the closed neighborhood of the vertex u∈V(G), and N*(u)=N(u)∪{u} are called as neighborhood and closed neighborhood of u in G.


## 2. On ConnectedHPK(n1,n2,n3,n4)[Kt]-Residual Graphs

Definition 4.
A graphG is a 3-dimensional hyperplane complete graph, if for every x∈V(G), V(G)=V1×V2×V3×V4, x={(x1,x2,x3,x4)∣xi∈Vi,i=1,2,3,4}, |Vi|=ni,  i=1,2,3,4. Two vertices x=(x1,x2,x3,x4) and y=(y1,y2,y3,y4) are adjacent to each other, if and only if x≠y and xk=yk for some k=1,2,3,4. For convenience, it writes HPK(n1,n2,n3,n4) instead of 3-dimensional hyperplane complete graphs.Definition 5.
LetF=HPK(n1,n2,n3,n4), a graph G is HPK(n1,n2,n3,n4)-residual graph, if for every u∈G, it is G-N*(u)≅F. A multiply HPK(n1,n2,n3,n4)-residual graph is m-HPK(n1,n2,n3,n4)-residual graph, if the removal of the closed neighborhood of any vertex of G results in an (m-1)-HPK(n1,n2,n3,n4)-residual graph.By Definitions4 and 5, let G=HPK(n1,n2,n3,n4) and n=v(G)=n1n2n3n4, if ni=1 for some i, then G is indeed a complete graph Kn. In fact, HPK(m,l)=Km×Kl, and HPK(l) is an empty graph with n vertices.Definition 6.
LetG1=(V1,E1) and G2=(V2,E2) are simple graphs. In the composition [17], G1 and G2 are recorded as G=G1[G2], G1[G2]=V1×V2, and u=(u1,u2) is adjacent to v=(v1,v2) in G, if and only if u1=v1, u2≠v2, u2 is adjacent to v2 in G2, but u1 is adjacent to v1 in G1.By Definitions4, 5, and Theorem 3, we have the following.Lemma 7.
IfF is a connected noncomplete graph, then there is no disconnected F-residual graph.Proof.
Suppose thatG is an F-residual graph, if G is disconnected, let G=G1∪G2, where G1 is a connected component of the G. Then, for any v∈G1, so
(1)G-N*(v)=(G1∪G2)-NG1*(v)=G2∪(G1-NG1*(v))≅F.
Since F is connected, so V(G1)-NG1*(v)=ϕ and G2≅F. Thus, G2 is connected, and G2 is not a complete graph; hence, there are two vertices u and w in G2, and u is nonadjacent to w, let
(2)G-N*(u)=(G1∪G2)-NG2*(v)=G1∪(G2-NG2*(u)).
Since w∈G2-NG2*(u). Hence, G-N*(u) is disconnected; however G-N*(u)≅F is connected, which is a contraction.Theorem 8.
Assume thatHPK(n1+m),(n2+m),…,(nr+m)[Kt] is an m-HPK(n1,n2,…,nr)[Kt]-residual graph, particularly, HPK(2,2,…,2,n+1)[Kt] is a Knt-residual graph.Proof.
The proof follows using Definitions4, 5, 6, and HPK(1,1,…,1,n)[Kt]≅Knt.Lemma 9.
LetF=HPK(n1,n2,n3,n4)[Kt],n1,n2,n3,n4≥4. x,y,z,w is pairwise nonadjacent in F, then |N*(x)∩N*(y)∩N*(z)∩N*(w)|=24t.Proof.
By Definitions5 and 6 and let V(F)=V1×V2×V3×V4×V5, Vi=1,2,…,ni,  i=1,2,3,4, V5=1,2,…,t. Let x=(x1,x2,x3,x4,x5), y=(y1,y2,y3,y4,y5), z=(z1, z2, z3, z4, z5), x,y,z is pairwise nonadjacent in F, if and only if x≠y and xi=yi for some i=1,2,3,4, since x,y,z,w is pairwise nonadjacent, then x1≠y1≠z1≠w1, x2≠y2≠z2≠w2, x3≠y3≠z3≠w3, x4≠y4≠z4≠w4. And n1,n2,n3,n4≥4, hence,
(3)N*(x)∩N*(y)∩N*(z)∩N*(w)={(x1,y2,z3,w4,r),(x1,y2,w3,z4,r),(x1,z2,y3,w4,r),(x1,z2,w3,y4,r),(x1,w2,y3,z4,r),(x1,w2,z3,y4,r),(y1,x2,z3,w4,r),(y1,x2,w3,z4,r),(y1,z2,x3,w4,r),(y1,z2,w3,x4,r),(y1,w2,z3,x4,r),(y1,w2,x3,z4,r),(z1,x2,y3,w4,r),(z1,x2,w3,y4,r),(z1,y2,x3,w4,r),(z1,y2,w3,x4,r),(z1,w2,x3,y4,r),(z1,w2,y3,x4,r),(w1,x2,y3,z4,r),(w1,x2,z3,y4,r),(w1,y2,x3,z4,r),(w1,y2,z3,x4,r),(w1,z2,x3,y4,r),(w1,z2,y3,z4,r)∣r∈V5},
then |N*(x)∩N*(y)∩N*(z)∩N*(w)|=24t.Lemma 10.
Assume that G is anF-residual graph, F=HPK(n1,n2,n3,n4)[Kt],n1,n2, n3,n4≥4, x,y is pairwise nonadjacent in G, then |N*(x)∩N*(y)|=(n1+1)(n2+1)(n3+1)(n4+1)-2n1n2n3n4+(n1-1)(n2-1)(n3-1)(n4-1).Proof.
The proof follows using Definitions4, 5, and 6.Lemma 11.
Assume thatG is an F-residual graph, F=HPK(n1,n2,n3,n4)[Kt], n1, n2, n3, n4≥4, for any u∈V(G), then d(u)≥[(n1+1)(n2+1)(n3+1)(n4+1)-n1n2n3n4]t-1.Proof.
For anyv∈V(G), and v is nonadjacent to u in G, let F=G-N*(v)≅HPK(n1,n2,n3,n4)[Kt], then u∈V(F), by Definitions 6, then
(4)|V(F)-NF*(u)|=(n1-1)(n2-1)(n3-1)(n4-1)t,|NF*(u)|=n1n2n3n4t-(n1-1)(n2-1)(n3-1)(n4-1)t,
hence, dF(u)=n1n2n3n4t-(n1-1)(n2-1)(n3-1)(n4-1)t-1. Since v,u,w is pairwise nonadjacent in G, by Lemma 10, then |N*(u)∩N*(v)∩N*(w)|≥6(n1+n2+n3+n4)t, so
(5)d(u)=dF(u)+|N*(u)∩N*(v)|≥[n1n2n3n4-(n1-1)(n2-1)(n3-1)(n4-1)+(n1+1)(n2+1)(n3+1)(n4+1)-2n1n2n3n4+(n1-1)(n2-1)(n3-1)(n4-1)]t-1=[(n1+1)(n2+1)(n3+1)(n4+1)-n1n2n3n4]t-1.
This completes the proof.Theorem 12.
Let G isHPK(n1,n2,n3,n4)[Kt]-residual graph, n1,n2,n3,n4≥4, then v(G)≥(n1+1)(n2+1)(n3+1)(n4+1)t.Proof.
For anyu∈G, let G-N*(u)=F≅HPK(n1,n2,n3,n4)[Kt], by Theorem 3 and Lemma 11, then
(6)v(G)=d(u)+1+v(F)≥[(n1+1)(n2+1)(n3+1)(n4+1)-n1n2n3n4]t+n1n2n3n4t=(n1+1)(n2+1)(n3+1)(n4+1)t.Theorem 13.
Let G isHPK(n1,n2,n3,n4)[Kt]-residual graph,  n1,n2,n3,n4≥4 and v(G)=(n1+1)(n2+1)(n3+1)(n4+1)t, then G≅HPK(n1+1,n2+1,n3+1,n4+1)[Kt].In order to proof Theorem13, we have the following Lemma.Lemma 14.
Assume thatF=HPK(n1,n2,n3,n4)[Kt],  n1,n2,n3,n4≥4. x,y,z,w is pairwise nonadjacent in F, let x=(x1,x2,x3,x4,x5), y=(y1,y2,y3,y4,y5), z=(z1,z2,z3,z4,z5), w=(w1,w2,w3,w4,w5), then
(1)N(x)∩N(y)∩N(z)∩N(w)∩N*(X)={(w1,x2,y3,z4,r∣r∈V5)}, and X contains x2,y3,z4 54 set intersection, and
(7)N*(X)=N(x1,x2,x3,y4,r)∩N(x1,x2,z3,x4,r)∩N(x1,x2,z3,y4,r)∩N(y1,x2,x3,x4,r)∩N(y1,x2,x3,y4,r)∩N(y1,x2,z3,x4,r)∩N(y1,x2,z3,y4,r)∩N(z1,x2,x3,x4,r)∩N(z1,x2,x3,y4,r)∩N(z1,x2,z3,x4,r)∩N(z1,x2,z3,y4,r)∩N(x1,y2,y3,x4,r)∩N(x1,y2,y3,y4,r)∩N(x1,z2,y3,x4,r)∩N(x1,z2,y3,y4,r)∩N(y1,y2,y3,x4,r)∩N(y1,z2,y3,x4,r)∩N(y1,z2,y3,y4,r)∩N(z1,y2,y3,x4,r)∩N(z1,y2,y3,y4,r)∩N(z1,z2,y3,x4,r)∩N(z1,z2,y3,y4,r)∩N(x1,y2,x3,z4,r)∩N(x1,y2,z3,z4,r)∩N(x1,z2,x3,z4,r)∩N(x1,z2,z3,z4,r)∩N(y1,y2,x3,z4,r)∩N(y1,y2,z3,z4,r)∩N(y1,z2,x3,z4,r)∩N(y1,y2,z3,z4,r)∩N(z1,y2,x3,z4,r)∩N(z1,y2,z3,z4,r)∩N(z1,z2,x3,z4,r)∩N(x1,x2,y3,x4,r)∩N(x1,x2,y3,y4,r)∩N(y1,x2,y3,x4,r)∩N(y1,x2,y3,y4,r)∩N(z1,x2,y3,x4,r)∩N(z1,x2,y3,y4,r)∩N(x1,x2,x3,z4,r)∩N(x1,x2,z3,z4,r)∩N(y1,x2,x3,z4,r)∩N(y1,x2,z3,z4,r)∩N(z1,x2,x3,z4,r)∩N(z1,x2,z3,z4,r)∩N(x1,y2,y3,z4,r)∩N(x1,z2,y3,z4,r)∩N(y1,y2,y3,z4,r)∩N(y1,z2,y3,z4,r)∩N(z1,y2,y3,z4,r)∩N(z1,z2,y3,z4,r)∩N(x1,x2,y3,z4,r)∩N(y1,x2,y3,z4,r)∩N(z1,x2,y3,z4,r),(2)(8)N(w1,w2,w3,w4,r)∩N(x1,x2,x3,x4,r)∩N(w1,y2,y3,y4,r)∩N(y1,w2,y3,y4,r)∩N(w1,z2,z3,z4,r)∩N(z1,w2,z3,z4,r)-N(y1,y2,y3,y4,r)-N(z1,z2,z3,z4,r)={(w1,w2,x3,x4,r)∣r∈V5},(3)(9)M=N(w1,w2,w3,w4,r)∩N(x1,x2,x3,x4,r)∩N(w1,y2,y3,y4,r)∩N(y1,w2,y3,y4,r)∩N(y1,y2,w3,y4,r)∩N(w1,z2,z3,z4,r)∩N(z1,w2,z3,z4,r)∩N(z1,z2,w3,z4,r)-N(y1,y2,y3,y4,r)-N(z1,z2,z3,z4,r)={(w1,w2,w3,x4,r)∣r∈V5}.Proof.
Part (1) follows from Definition6 and Lemma 9.
Similarly,(10)N(x)∩N(y)∩N(z)∩N(w)∩N*(Y)={(x1,w2,y3,z4,r∣r∈V5)},N(x)∩N(y)∩N(z)∩N(w)∩N*(Z)={(x1,y2,w3,z4,r∣r∈V5)},N(x)∩N(y)∩N(z)∩N(w)∩N*(W)={(x1,y2,z3,w4,r∣r∈V5)},
where N*(Y) contains x1,y3,z4 54 set intersection, N*(Z) contains x1,y2,z4 54 set intersection, and N*(W) contains x1,y2,z3 54 set intersection.
(2) Letv=(v1,v2,v3,v4,v5)∈M, by Definition 6, and v is not adjacent y,z, hence, vi≠yi≠zi,i=1,2,3,4, and v=(v1,v2,v3,v4,v5) is adjacent to (w1,y2,y3,y4,r), (y1,w2,y3,y4,r), (w1,z2,z3,z4,r), (z1,w2,z3,z4,r), hence v1=w1,  v2=w2, because v is adjacent to x, then x1≠w1=v1, x2≠w2=v2, hence, v3=x3,  v4=x4, for any v5∈V5.
Part (3) follows from the proof of part (2).Proof of Theorem13.
We are now ready to prove the following quantitative version of our theorem, we have four cases as follows.
Case  1. For any u∈V(G), let F1=G-N*(u)=HPK(n1,n2,n3,n4)[Kt], by Definition 6, V(F1)={(x1,x2,x3,x4,x5)∣1≤xi≤ni,i=1,2,3,4;1≤x5≤t}, x=(x1,x2,x3,x4,x5) is adjacent to y=(y1,y2,y3,y4,y5) in F1, if and only if x≠y and for any xi=yi,  i=1,2,3,4.
Case  2. Let F2=G-N*(n1,n2,n3,n4,1)=HPK(n1,n2,n3,n4)[Kt], by Lemma 14, using V(F1)∩V(F2) in the name of the vertex of V(F2)-V(F1) in the naming of vertices. First, prove that u=(0,0,0,0,1), for any x,y∈V(F1)∩V(F2), x=(x1,x2,x3,x4,1), y=(y1,y2,y3,y4,1), xi≠yi,  i=1,2,3,4. For convenience, N(x1,x2,x3,x4,x5) is the closed neighborhood of a vertex (x1,x2,x3,x4,x5), N*(x1, x2, x3, x4, x5)=N(x1, x2, x3, x4, x5)∪(x1,x2,x3,x4,x5), by Lemma 14, let
(11)N(u)∩N(x)∩N(y)∩N(z)∩N*(X)={(0,x2,y3,z4,r)∣1≤r≤t},N(u)∩N(x)∩N(y)∩N(z)∩N*(Y)={(x1,0,y3,z4,r)∣1≤r≤t},N(u)∩N(x)∩N(y)∩N(z)∩N*(Z)={(x1,y2,0,z4,r)∣1≤r≤t},N(u)∩N(x)∩N(y)∩N(z)∩N*(W)={(x1,y2,z3,0,r)∣1≤r≤t},(12)N(0,0,0,0,1)∩N(x1,x2,x3,x4,1)∩N(0,y2,y3,y4,1)∩N(y1,0,y3,y4,1)∩N(0,z2,z3,z4,1)∩N(z1,0,z3,z4,1)-N(y1,y2,y3,y4,1)-N(z1,z2,z3,z4,1)={(0,0,x3,x4,r)∣1≤r≤t},N(0,0,0,0,1)∩N(x1,x2,x3,x4,1)∩N(y1,0,y3,y4,1)∩N(y1,y2,0,y4,1)∩N(z1,0,z3,z4,1)∩N(z1,z2,0,z4,1)-N(y1,y2,y3,y4,1)-N(z1,z2,z3,z4,1)={(x1,0,0,x4,r)∣1≤r≤t},N(0,0,0,0,1)∩N(x1,x2,x3,x4,1)∩N(y1,y2,0,y4,1)∩N(y1,y2,y3,0,1)∩N(z1,z2,0,z4,1)∩N(z1,z2,z3,0,1)-N(y1,y2,y3,y4,1)-N(z1,z2,z3,z4,1)={(x1,x2,0,0,r)∣1≤r≤t},N(0,0,0,0,1)∩N(x1,x2,x3,x4,1)∩N(0,y2,y3,y4,1)∩N(y1,y2,0,y4,1)∩N(0,z2,z3,z4,1)∩N(z1,z2,0,z4,1)-N(y1,y2,y3,y4,1)-N(z1,z2,z3,z4,1)={(0,x2,0,x4,r)∣1≤r≤t},N(0,0,0,0,1)∩N(x1,x2,x3,x4,1)∩N(0,y2,y3,y4,1)∩N(y1,y2,y3,0,1)∩N(0,z2,z3,z4,1)∩N(z1,z2,z3,0,1)-N(y1,y2,y3,y4,1)-N(z1,z2,z3,z4,1)={(0,x2,x3,0,r)∣1≤r≤t},N(0,0,0,0,1)∩N(x1,x2,x3,x4,1)∩N(y1,0,y3,y4,1)∩N(y1,y2,y3,0,1)∩N(z1,0,z3,z4,1)∩N(z1,z2,z4,0,1)-N(y1,y2,y3,y4,1)-N(z1,z2,z3,z4,1)={(x1,0,x3,0,r)1≤r≤t},(13)N(0,0,0,0,1)∩N(x1,x2,x3,x4,1)∩N(0,y2,y3,y4,1)∩N(y1,0,y3,y4,1)∩N(y1,y2,0,y4,1)∩N(0,z2,z3,z4,1)∩N(z1,0,z3,z4,1)∩N(z1,z2,0,z4,1)-N(y1,y2,y3,y4,1)-N(z1,z2,z3,z4,1)={(0,0,0,x4,r)∣1≤r≤t},N(0,0,0,0,1)∩N(x1,x2,x3,x4,1)∩N(y1,0,y3,y4,1)∩N(y1,y2,0,y4,1)∩N(y1,y2,y3,0,1)∩N(z1,0,z3,z4,1)∩N(z1,z2,0,z4,1)∩N(z1,z2,z3,0,1)-N(y1,y2,y3,y4,1)-N(z1,z2,z3,z4,1)={(x1,0,0,0,r)∣1≤r≤t},N(0,0,0,0,1)∩N(x1,x2,x3,x4,1)∩N(0,y2,y3,y4,1)∩N(y1,0,y3,y4,1)∩N(y1,y2,y3,0,1)∩N(0,z2,z3,z4,1)∩N(z1,0,z3,z4,1)∩N(z1,z2,z3,0,1)-N(y1,y2,y3,y4,1)-N(z1,z2,z3,z4,1)={(0,0,x3,0,r)∣1≤r≤t},N(0,0,0,0,1)∩N(x1,x2,x3,x4,1)∩N(0,y2,y3,y4,1)∩N(y1,y2,0,y4,1)∩N(y1,y2,y3,0,1)∩N(0,z2,z3,z4,1)∩N(z1,z2,0,z4,1)∩N(z1,z2,z3,0,1)-N(y1,y2,y3,y4,1)-N(z1,z2,z3,z4,1)={(0,x2,0,0,r)∣1≤r≤t}.
Lastly let {v∈V(F2)∣NF2*(v)=NF2*(u)}={(0,0,0,0,r)∣1≤r≤t}, so far V(F2)-V(F1) vertex already all named, the uniqueness of the name. By Lemma 14 and Definition 6, then F2≅HPK(n1,n2,n3,n4)[Kt], V(F2)={(x1,x2,x3,x4,x5)∣0≤xi≤xni,i=1,2,3,4;1≤x5≤t}. Two vertices x=(x1,x2,x3,x4,x5) and y=(y1,y2,y3,x4,x5) are adjacent to each other, if and only if exist x≠y and xi=yi for i=1,2,3,4.
Case  3. Let F3=G-N*(1,1,1,1,1)≅HPK(n1,n2,n3,n4)[Kt], to F3 not named point naming, these point sets are composed of
(14)V(F3)-V(F1)-V(F2)=V(F3)∩(V(F1)∪V(F2))¯=V(F3)∩(N*(0,0,0,0,1)∩N*(n1,n2,n3,n4,1)∩N*(m1,m2,m3,m4,1))=N*(0,0,0,0,1)∩N*(n1,n2,n3,n4,1)∩N*(m1,m2,m3,m4,1)-N*(1,1,1,1,1),
for any x=(x1,x2,x3,n4,1)∈V(F1)∩V(F2)∩V(F3), 2≤xi≤ni-1,  i=1,2,3,4. By Lemma 14 and (11), we can name
(15){(0,x2,n3,m4,r),(x1,0,n3,m4,r),(x1,n2,0,m4,r),(x1,n3,m4,0,r)∣1≤r≤t}.
By Lemma 14 and (12), we can name
(16){(0,0,n3,m4,r),(0,n2,m3,0,r),(0,n2,0,m4,r),(n1,0,0,m4,r),(n2,m2,0,0,r),(n1,0,m3,0,r)∣1≤r≤t}.
By Lemma 14 and (13), we can name
(17){(0,0,0,m4,r),(0,0,m3,0,r),(0,m2,0,0,r),(m1,0,0,0,r)∣1≤r≤t}.
Similarly, we can name
(18){(0,n2,n3,n4,r),(n1,0,n3,n4,r),(n1,n2,0,n4,r),(n1,n2,n3,0,r)∣1≤r≤t}.
For the V(F2)∩V(F3) point rename, by Lemma 14 and the uniqueness of the name get the name and in F2 name is the same, then V(F3)={(x1,x2,x3,x4,x5)∣0≤xi≤ni,xi≠1,i=1,2,3,4;1≤x4≤t}, and two vertices x=(x1,x2,x3,x4,x5), y=(y1,y2,y3,y4,y5) are adjacent to each other in the F3, if and only if x≠y and, for any xi=yi, for i=1,2,3,4.
Case  4. Named G all unnamed point, this kind of composition is set N*(0,0,0,0,1)∩N*(n1,n2,n3,n4,1)∩N*(1,1,1,1,1). Let F4=G-N*(2,2,2,2,1)=HPK(n1,n2,n3,n4)[Kt]. Obviously, (0,0,0,0,1),(n1, n2, n3, n4, 1), (1,1,1,1,1)∈V(F4). By Lemmas 9 and 14, then
(19)|NF4*(0,0,0,0,0,1)∩NF4*(n1,n2,n3,n4,1)∩NF4*(1,1,1,1,1)|=24t,NF4*(0,0,0,0,1)∩NF4*(n1,n2,n3,n4,1)∩NF4*(1,1,1,1,1)⊂V(F4).
As described in Case  3, in accordance with the Lemma 14, we name V(F2)∩V(F4), V(F3)∩V(F4) the same as in F2,F3. Similarly, by Lemma 14 and (11), we can name
(20)(0,1,n3,n4,r),(0,n2,1,n4,r),(0,n2,n3,1,r),(1,0,n3,n4,r),(1,n2,n3,0,r),(1,n2,0,n4,r),1≤r≤t.
Hence,
(21)V(F4)={(x1,x2,x3,x4,x5)∣0≤xi≤ni,xi≠2,i=1,2,3,4,1≤x4≤t},
two vertices x=(x1,x2,x3,x4,x5), y=(y1,y2,y3,y4,y5) are adjacent to each other in F4, if and only if, exist x≠y and xi=yi for i=1,2,3,4.
So far, we have theG of each vertex named and V(G)={(x1,x2,x3,x4,x5)∣0≤xi≤ni,i=1,2,3,4,1≤x4≤t}). According to the naming rules, for any x=(x1,x2,x3,x4,x5), y=(y1,y2,y3,y4,y5), if x and y in the same Fi,i=1,2,3,4,5, x is adjacent to y, if and only if x≠y and for any xi=yi, for i=1,2,3,4. Otherwise, for any z∈V(G), z is not adjacent x, y. Let G1=G-N*(z)≅HPK(n1,n2,n3,n4)[Kt], then x,y∈V(G1), the uniqueness of the name also get x and y is adjacent to in G. So x is adjacent to y in G, if and only if x≠y and for any xi=yi, for i=1,2,3,4.
With comprehensive discussed above, thenG≅HPK(n1+1,n2+1,n3+1,n4+1)[Kt]. The proof is complete.


## 3. Connectedm-HPK(n1,n2,n3,n4)[Kt]-Residual Graphs

Lemma 15.
Assume that graphG is m-HPK(n1,n2,n3,n4)[Kt]-residual graph, n1,n2,n3,n4≥4, x,y,z, and w is pairwise nonadjacent in G, then |N*(x)∩N*(y)∩N*(z)∩N*(w)|≥24t.Proof.
By Definitions4, 5, 6, and n1,n2,n3,n4≥4, we can turn out vertex u1,u2,…,um+2,um+3, ui+1∈Gi=Gi-1-N*(ui),  i=1,2,…,m+2,m+3, let G0=G, u1∈G0, for convenience, u1∈V(G0) instead of u∈G, let u1,u2,…,um+2,um+3 be pairwise nonadjacent. Let x=u1,y=u2,z=u3, hence
(22)F=G-N*(u4)-⋯-N*(um+2)-N*(um+3)≅HPK(n1,n2,n3,n4)[Kt],x,y,z,w is pairwise nonadjacent in F, by Lemma 9, then
(23)|N*(x)∩N*(y)∩N*(z)∩N*(w)|≥NF*(x)∩NF*(y)∩NF*(z)∩NF*(w)≥24t.Lemma 16.
Assume that graphG is m-HPK(n1, n2, n3, n4)[Kt]-residual graph, n1, n2, n3, n4≥4, u,v∈V(G) is pairwise nonadjacent in G, then |N*(u)∩N*(v)|≥[(n1+m+1)(n2+m+1)(n3+m+1)(n4+m+1)-2(n1+m)(n2+m)(n3+m)(n4+m)+(n1+m-1)(n2+m-1)(n3+m-1)(n4+m-1)]t.Proof.
Form=1, by Lemma 10, we are done. Suppose that m≥1, it is true. For m+1, let G be a connected (m+1)-HPK(n1, n2, n3, n4)[Kt]-residual graph, x,y,z is pairwise nonadjacent in G, for any w∈G, w is not adjacent x,y,z in G. Let H=G-N*(w), then x,y is pairwise nonadjacent in H, H is m-HPK(n1,n2,n3,n4)[Kt]-residual graph. By inductive hypothesis, |N*(u)∩N*(v)|≥[(n1+m+1)(n2+m+1)(n3+m+1)(n4+m+1)-2(n1+m)(n2+m)(n3+m)(n4+m)+(n1+m-1)(n2+m-1)(n3+m-1)(n4+m-1)]t.Lemma 17.
Assume that graphG is m-HPK(n1, n2, n3, n4)[Kt]-residual graph, n1, n2, n3, n4≥4, u∈V(G), then d(u)≥[(n1+m)(n2+m)(n3+m)(n4+m)-(n1+m-1)(n2+m-1)(n3+m-1)(n4+m-1)]t-1.Proof.
Form=1, by Lemma 14, we are done. Suppose that m≥1, it is true. For m+1, let G be a connected (m+1)-HPK(n1,n2,n3,n4)[Kt]-residual graph, u,v,w is pairwise nonadjacent in G. Let H=G-N*(v), then u∈H, H is m-HPK(n1,n2,n3,n4)[Kt]-residual graph. By inductive hypothesis and by Lemma 16, then
(24)d(u)=dH(u)+|N*(u)∩N*(v)∩N*(w)|≥[(n1+m)(n2+m)(n3+m)(n4+m)-(n1+m-1)(n2+m-1)×(n3+m-1)(n4+m-1)]t-1+[(n1+m+1)(n2+m+1)(n3+m+1)(n4+m+1)-2(n1+m)(n2+m)(n3+m)(n4+m)+(n1+m-1)(n2+m-1)×(n3+m-1)(n4+m-1)]t=[(n1+m+1)(n2+m+1)(n3+m+1)(n4+m+1)-(n1+m)(n2+m)(n3+m)(n4+m)]t-1.Theorem 18.
LetG is m-HPK(n1,n2,n3,n4)[Kt]-residual graph, n1, n2, n3, n4≥4, then v(G)≥(n1+m)(n2+m)(n3+m)(n4+m)t.Proof.
Form=1, by Theorem 12, we are done. Suppose that m≥1, it is true. For m+1, let G be a connected (m+1)-HPK(n1,n2,n3,n4)[Kt]-residual graph, for any u∈G. Let H=G-N*(u), H is m-HPK(n1,n2,n3,n4)[Kt]-residual graph. By inductive hypothesis and by Lemma 17, then
(25)v(H)≥(n1+m)(n2+m)(n3+m)(n4+m)t,|N*(u)|≥[(n1+m+1)(n2+m+1)×(n3+m+1)(n4+m+1)-(n1+m)(n2+m)(n3+m)(n4+m)]t,v(G)≥P(H)|N*(u)|≥(n1+m+1)(n2+m+1)(n3+m+1)(n4+m+1)t.Theorem 19.
LetG is m-HPK(n1,n2,n3,n4)[Kt]-residual graph, n1,n2,n3,n4≥4, v(G)=(n1+m)(n2+m)(n3+m)(n4+m)t, then G≅HPK(n1+m,n2+m,n3+m,(n4+m))[Kt].Proof.
Form=1, by Theorem 12, we are done. Suppose that m≥1, it is true. For m+1, let G be a connected (m+1)-HPK(n1,n2,n3,n4)[Kt]-residual graph, n1,n2,n3,n4≥4, v(G)=(n1+m+1)(n2+m+1)(n3+m+1)(n4+m+1)t, for any u∈G. Let H=G-N*(u), H is m-HPK(n1,n2,n3,n4)[Kt]-residual graph. By inductive hypothesis and by Lemma 17, then
(26)v(H)=v(G)-|N*(u)|≤(n1+m+1)(n2+m+1)(n3+m+1)(n4+m+1)t-[(n1+m+1)(n2+m+1)(n3+m+1)(n4+m+1)-(n1+m)(n2+m)(n3+m)(n4+m)]t=(n1+m)(n2+m)(n3+m)(n4+m)t,
by Theorem 18, v(H)=(n1+m)(n2+m)(n3+m)(n4+m)t. By inductive hypothesis, H≅HPK(n1+m,n2+m,n3+m,n4+m)[Kt]. By Definition 6, let G be a connected HPK(n1+m,n2+m,n3+m,,n4+m)[Kt]-residual graph, ni+m≥ni≥4, with conditions and Theorem 12, then G≅HPK(n1+m+1,n2+m+1,n3+m+1,n4+m+1)[Kt].



---

*Source: 983830-2013-03-12.xml*