Vol. 37 ( 2017 ) No. 4 J. of Math. (PRC) 1, 1, 1, 2 (1., 400065) (2., 400067) :, Erdös Harary Klawe s.,,,. : ; ; ; MR(2010) : 05C35; 05C60; 05C75 : O157.5 : A : 0255-7797(2017)04-0833-12 1 1980, Erdös, Harary Klawe [1],, m n, (m + 1)K n (m + 1)n m K n -, C 5 5 K 2 -. n > 1, n 2, K n - 2(n + 1); n 2, 3, 4, K n+1 K 2 K n -. [2 10], [2], ; [3] K n -, n > 3, K n -. [4] K n -, n < 11, ; [5] K n -, n 11., [6 7]. Erdös, [8 9] ; [8] 3 ; [9] 3 K t., (n 1 + 1)(n 2 + 1) (n r + 1),,, (n 1 + m)(n 2 + m) (n r + m),. 2 : 2015-08-24 : 2015-12-21 : (11671001; 61472056); (cstc2015jcyja00034; cstc2015jcyja00015); (KJ1600425; KJ1500403). : (1976 ),,,, :.
834 Vol. 37 2.1 G = (V, E), u V = V (G), N(u) = {x x V (G), x u } N (u) = {u} N(u) u. 2.2 F, u V (G), G u N (u) F [10 11], G F -., G m F -, u V (G), G N (u) (m 1) F -. 1 F - F -. 2.3 G r 1, x V (G), V (G) = V 1 V 2 V r, x = {(x 1, x 2,, x r ) x i V i, i = 1, 2,, r}, V i = n i, i = 1, 2,, r, x = (x 1, x 2,, x r ) y = (y 1, y 2,, y r ) x y, k = 1, 2,, r, x k = y k., HP K(n 1, n 2,, n r ) r 1. 2.4 G 1 = (V 1, E 1 ), G 2 = (V 2, E 2 ), G 1 G 2 G = G 1 [G 2 ], V (G) = V 1 V 2 = {x = (x 1, x 2 ) (x 1 V 1, x 2 V 2 }, u = (u 1, u 2 ) v = (v 1, v 2 ) u 1 v 1 G 1, u 1 = v 1, u 2 v 2 G 2. 2.5 G = (V, E), S V = V (G), S x, y S G, S = k, S G k -. 2.6 G 1 = (V 1, E 1 ), G 2 = (V 2, E 2 ), G = G 1 + G 2, V (G) = V 1 V 2, E(G) = E 1 E 2 E[K(V 1, V 2 )], K(V 1, V 2 ) V 1 V 2. [1]. 2.1 [1] G F -, d(u) = ν(g) ν(f ) 1, u V (G), ν(g) G. [1 8]. 3 2.3. 3.1 G HP K(n 1, n 2, n r ) -, n 1, n 2, n r r 3, u, v V (G), w G, u, v V (G) N (w).. 3.2 G = HP K(n 1 + 1, n 2 + 1,, n r + 1), n 1, n 2,, n r 1, r 2, G HP K(n 1, n 2,, n r ) -. V (G) = V 1 V 2 V r, V i = n i +1, x = (x 1, x 2, x r ) y = (y 1, y 2,, y r ), x i y i, i = 1, 2,, r, v = (v 1, v 2,, v r ) G, G 1 = G N (v) = (x 1, x 2,, x r ) x i V i, x i v i, i = 1, 2,, r = V 1 V 2 V r, V i = V i {v i } V i, i = 1, 2,, r, x = (x 1, x 2,, x r ) G 1 y = (y 1, y 2,, y r ) G 1, G 1 G, G, G 1 = HP K(n1, n 2,, n r ), G HP K(n 1, n 2,, n r ) -..
No. 4 : 835 3.3 G = HP K(n 1, n 2, n r ), {v 1, v 2,, v r, v 0 } G r + 1, N (v 1 ) N (v 2 ) N (v r ) N (v 0 ) = φ. x = (x 1, x 2,, x r ) N (v 1 ) N (v 2 ) N (v r ) N (v 0 ), v k = (v1, k v2, k, vr k ), k = 0, 1,, r, G, x ik = vi k k, 1 i k r, k = 0, 1,, r, i k = i l = h, k l, k, l, vh k = vl h = x h, vh k vh l G,.. 3.4 H = HP K(n 1 + 1, n 2 + 1,, n r + 1), {v, v 1, v 2,, v r } H (r + 1) -, H i = H N (v i ), i = 1, 2,, r, N (v) = N H 1 (v) (N H 2 (v)) N H 2 (v 1 ) (N H k (v) N H k (v 1 ) N H k (v k 1 )) (N H r (v) N H r (v 1 ) N H r (v r 1 )). V (H) = V (H i ) N (v i ), v V (H i ), N (v) = N (v) V (H) = N (v) (V (H 1 ) N (v 1 )) = (N (v) V (H 1 )) (N (v) (N (v 1 )) = (N H 1 (v) (N (v) (N (v 1 )) N (v) N (v 1 ) N (v i ) = (N H i+1 (v) (N H i+1 (v 1 ) N H i+1 (v i )) (N (v) N (v 1 ) N (v i ) N (v i+1 )), i = 1, 2, r. 3.5 G = H = HP K(n 1, n 2, n r ), {v 1, v 2,, v k } V (G), {u 1, u 2,, u k } V (H) G H k -, N G(v 1 ) N G(v 2 ) N G(v k ) = N H(v 1 ) N H(v 2 ) N H(v k ). k - {v 1, v 2,, v k } V (G), G k -, g k, g k = g(v 1, v 2,, v k ) = N (v 1 ) N (v 2 ) N (v k ), g k, k = 1, g 1 = g(v) = N (v) = ν(g) ν(g N (v)) = n 1 n 2 n r (n 1 1)(n 2 1) (n r 1), g 1 = g(v)., g k, 3.3 1 < k < r + 1, g k = 0. G k = G N (v 1 ) N (v 2 ) N (v k ), G k = HP K(n 1 k, n 2 k,, n r k) ν(g k ) = (n 1 k)(n 2 k) (n r k) = v k, = N (v 1 ) N (v 2 ) N (v k ) k g(v i ) g(v i, v j ) + + ( 1) l 1 i=1 1 i 1<i 2< <i l k 1 i<j k = ν(g) ν(g k ) = v v k. g(v i1, v i2,, v il ) + + ( 1) k 1 g(v 1, v 2,, v k )
836 Vol. 37 G = H, σ : V (H) V (G), u 1 u 2 H σ(u 1 ) σ(u 2 ) G. v i = σ(u i ), i = 1, 2,, r, {v 1, v 2,, v k } V (G) k - {u 1, u 2,, u k } V (H) k -, N G(v 1 ) N G(v 2 ) N G(v k ) = N H(u 1 ) N H(u 2 ) N H(u k ). 3.1 G HP K(n 1, n 2,, n r ) -, n 1, n 2,, n r r 3, ν(g) (n 1 + 1)(n 2 + 1) (n r + 1). v G, G N (v) = F = HP K(n 1, n 2,, n r ), V (F ) = {(x 1, x 2,, x r ) 1 x i n i, i = 1, 2,, r}, x = (x 1, x 2,, x r ) y = (y 1, y 2,, y r ) F x i y i, i = 1, 2,, r. v k = (k, k,, k), k = 1, 2,, r, {v, v 1, v 2,, v r } G r + 1 -. 3.4 3.5 F i = G N (v i ) = HP K(n 1, n 2,, n r ), i = 1, 2,, r. N (v) = N F 1 (v) (N F 2 (v) N F 2 (v 1 )) (N F k (v) N F k (v 1 ) N F k (v k 1 )) (N F r (v) N F r (v 1 ) N F r (v r 1 )) (N (v) N (v 1 ) N (v r )). H = HP K(n 1 + 1, n 2 + 1,, n r + 1), N (v) = N F 1 (v) + N F 2 (v) N F 2 (v 1 ) + + (N F k (v) N F k (v 1 ) N F k (v k 1 ) + + (N F r (v) N F r (v 1 ) N F r (v k 1 ) + N (v) N (v 1 ) N (v r ) = N H(u) + N (v) N (v 1 ) N (v r ), ν(g) = ν(f ) + N G(v) = ν(f ) + N H(u) + N (v) N (v 1 ) N (v r ) n 1 n 2 n r + (n 1 + 1)(n 2 + 1) (n r + 1) n 1 n 2 n r = (n 1 + 1)(n 2 + 1) (n r + 1).. r 1,,., G HP K(n 1, n 2,, n r ) -, n 1, n 2,, n r r 3, G. G, V (G) = V 1 V 2 V r = {(x 1, x 2,, x r ) 0 x i n i, i = 1, 2,, r}.
No. 4 : 837 x = (x 1, x 2,, x r ) y = (y 1, y 2,, y r ) x i y i, i = 1, 2,, r. u G, G N (u) = H = HP K(n 1, n 2,, n r ). H V (H) = {(x 1, x 2,, x r ) 1 x i n i, i = 1, 2,, r}, (3.1) H G, (3.1) G. H = G N (v), G, N (v). v k = (k, k,, k), k = 1, 2,, r, 3.4 H k = G N (v k ) = HP K(n 1, n 2,, n r ), k = 1, 2,, r. N (v) = N H 1 (v) (N H 2 (v) N H 2 (v 1 )) (N H k (v) N H k (v 1 ) N H k (v k 1 )) (N H r (v) N H r (v 1 ) N H r (v r 1 )) (N (v) N (v 1 ) N (v r )). (3.2) 3.5 N (v) = ν(g) ν(h) = (n 1 + 1)(n 2 + 1) (n r + 1) n 1 n 2 n r. 3.3 N (v) N (v 1 ) N (v r ) = φ, (3.2), (3.2) N (v) = N H 1 (v) (N H 2 (v) N H 2 (v 1 )) (N H k (v) N H k (v 1 ) N H k (v k 1 )) (N H r (v) N H r (v 1 ) N H r (v r 1 ). (3.3) G, H = G N (v) H k = G N (v k ), N (v k ), H = HP K(n 1, n 2,, n r ), n 1, n 2,, n r r 3, V (H) = {(x 1, x 2,, x r ) 1 x i n i, i = 1, 2,, r}, x = (x 1, x 2,, x r ) y = (y 1, y 2,, y r ) x i y i, i = 1, 2,, r. v = v 1 = (1, 1,, 1), F 1 = H N (v 1 ) = (x 1, x 2,, x r ) 2 x i n i, i = 1, 2,, r,. 3.1 R 1 : i 1, i 2,, i l, i l+1,, i r {1, 2,, r}, 1 i 1 < i 2 < < i l r, 1 i l+1 < < i r r, 1 l r 1. R 2 : a 1, a 2,, a l, 2 a k n ik, k = 1, 2,, l. R 3 : Y = {(y 1, y 2,, y r ) F 1 y ir a k, k = 1, 2,, l}. R 4 : b 1, b 2,, b r, 1 b k n ik, b k a k, k = 1, 2,, l. R 5 : u k = (u k 1, u k 2,, u k r), k = 1, 2,, l, u k i k = a k, u k i t = b t, 1 t l, t k, u k i l+1 = = u k i r = 2, x NF (v),
838 Vol. 37 R 6 : x u 1, u 2,, u l. R 7 : x Y. 3.1, x = (x 1, x 2,, x r ), x ik = a k, k = 1, 2,, l, x il+1 = = x ir = 1, x C 6 C 7, x, x Y, x il+1 = = x ir = 1. x ik = a k, x y Y, x ik a k 1, x ik b k, x u k, x ik = a k, k = 1, 2,, l,. N (v 1 ) 3.1 R 1, R 2, R 3, b 1, b 2,, b l, u 1, u 2,, u l, R 1, R 2, R 3, G,. 3.2 3.1 R 1, R 2, R 3 N(v 1 ), N (v 1 ), 3.1 R 1, R 2, R 3. 3.2 3.1,. x = (x 1, x 2,, x r ) N(v 1 ), N(v 1 ), 3.1 R 1, R 2, R 3. R 1 : i 1, i 2,, i l, i l+1,, i r, 1 i 1 < i 2 < < i l r, 1 i l+1 < < i r r, 1 l r 1, x il+1 = = x ir = 1, x i1, x i2,, x i1 1. R 2 : a 1, a 2,, a l, a k = x ik, 2 a k n ik, k = 1, 2,, l. R 3 : Y = {(y 1, y 2,, y r ) F 1 y ik a k, k = 1, 2,, l}. 3.1 3.2 N (v k ), v k = (k, k,, k), k = 1, 2,, r. N H (v) x, H = HP K(n 1, n 2,, n r ), n 1, n 2,, n r r 3, v H, H N (v), 3.1 3.2. N(v) N (v), v = (0, 0,, 0), N(v). H = G N (v), H k = G N (v k ), G, N Hk (v), (3.1), (3.3) N H1 (v),. 3.3. 3.1 3.2 1 0 N H1 (v) H = G N (v 1 ), v 1 = (1, 1,, 1), V (H 1 ) = {(x 1, x 2,, x r ) 0 x i n i, x i 1}. N H1 (v) V (H 1 ) N (v) = V (H) N (v 1 ) = G N (v) N (v 1 ), H = G N (v), 3.1 3.2 1 0. N H2 (v) N H2 (v 1 ). H 2 = G N (v 2 ) = HP K(n 1, n 2,, n r ), v 2 = (2, 2,, 2), H N (v k ) = G N (v) N (v k ) = H k N (v) = F k, V (H 2 ) = {(x 1, x 2,, x r ) 0 x i n i, x i 2, i = 1, 2,, r},
No. 4 : 839 N H 2 (v) N H 2 (v 1 ), V (H 2 ) N H 2 (v) = V (H) N H (v 2), H 2. 3.4 R 1 : i 1, i 2,, i l, i l+1,, i r. R 2 : a 1, a 2,, a l, 1 a k n ik, a k 2, k = 1, 2,, l, 1 {a 1, a 2,, a l }. R 3 : Y = {(y 1, y 2,, y r ) F 2 y ik a k, k = 1, 2,, l}. 3.4 3.2 R 2 1 {a 1, a 2,, a l }, R 1,R 2,R 3 x NH 2 (v) NH 2 (v 1 )., G, NH 2 (v) x, NH 2 (v) NH 2 (v 1 ) x, x H 1 H 2. x H 1 H 2, 3.4 H 2. H 1 : x H 1 (x 1, x 2,, x r ). x v 2 = (2, 2,, 2) H 1, H 1. 3.5 R 1 : i 1, i 2,, i l, i l+1,, i r, x i1, x i2,, x il 0, 1, 2, x il+1 = = x il = 0. R 2 : a 1, a 2,, a l, a k = x ik 0, 1, 2, k = 1, 2,, l. R 3 : Y = {(y 1, y 2,, y r ) F 2 y ik a k, k = 1, 2,, l}. x H 1 H 2, H 2 x = (x 1x 2 x r), x i k = a k, k = 1, 2,, l x i l+1 = = x i l = 0 a k 0, 1, 2, x v 1 = (1, 1,, 1) H 2, x (NH 1 (v) NH 2 (v)), x = x, x H 1 H 2. N H 2 (v) N H 2 (v 1 ), N H k (v) N H k (v 1 ) N H k (v k 1 ) N H 2 (v) N H 2 (v 1 ), 3.5 R 2 R 3. 3.6 R 1 : i 1, i 2,, i l, i l+1,, i r, x i1, x i2,, x il 0, 1, 2, x il+1 = = x il = 0. R 2 : a 1, a 2,, a l, 1 a t n it, a t k, {1, 2,, k 1} {a 1, a 2,, a k }. R 3 : Y = {(y 1, y 2,, y r ) F k y it a t, t = 1, 2,, l}. x = (x 1, x 2,, x r ), x NH k (v) NH k (v 1 ) NH k (v k 1 ),, k = r, (3.3) NH r (v) NH r (v 1 ) NH r (v r 1 ). 3.7 R 1 : i 1, i 2,, i r 1, i r, 1 i 1 < i 2 < < i r 1 r, 1 i r r. R 2 : a 1, a 2,, a r 1, {a 1, a 2,, a r 1 } = {1, 2,, r 1}. R 3 : Y = {(y 1, y 2,, y r ) F r y ik a k, k = 1, 2,, r 1}. R 1, R 2, R 3, H r, H r = G N (v k ), N (v k ), G H r N (v k ), V (G) = {(x 1, x 2,, x r ) 0 x i n i }, G x = (x 1, x 2,, x r ) y = (y 1, y 2,, y r ) x i y i, i = 1, 2,, r.
840 Vol. 37. 3.2 G HP K(n 1, n 2,, n r ) -, n 1, n 2,, n r r 3, ν(g) = (n 1 + 1)(n 2 + 1) (n r + 1), G = HP K(n 1 + 1, n 2 + 1,, n r + 1), G. G x y, 3.1, w, w x y. w H k, H k, k, x H k y H k, H k. H = G N (w) = HP K(n 1, n 2, n r ), x, y H. G H k, G, H = G N (w), G H, x, y H = G N (w),, x = (x 1, x 2,, x r ) y = (y 1, y 2,, y r ), G, G = HP K(n 1 + 1, n 2 + 1, n r + 1), HP K(n 1 + 1, n 2 + 1, n r + 1) r 1. 4,. 4.1 G HP K(n 1, n 2,, n r ) -, n 1, n 2,, n r r + 2 5, ν(g) = k(n 1 + 1)(n 2 + 1) (n r + 1), G = G 1 + G 2 + + G k, G i = HP K(n1 + 1, n 2 + 1,, n r + 1), i = 1, 2,, k.,. 4.1 H = HP K(n 1, n 2,, n r ), V (H) = {(x 1, x 2,, x r ) 1 x i n i, i = 1, 2,, r}, S 1 = {v 1, v 2,, v r, v 0 } S 2 = {u 1, u 2,, u r, u 0 }, S 1 S 2 (r + 1) -. S 2 S 1, u i = v i, i = 0, 1, 2,, r; i k, l, u i = (u i 1, u i 2,, u i r), v i = (v1, i v2, i, vr), i i = 0, 1, 2,, r, u k j = vj k vj l x j, u l j = vj l vj k y j, j = 1, 2,, r, x j, y j vj, i i = 0, 1, 2,, r, u k j u l j. 4.1,. 4.1 H = HP K(n 1, n 2,, n r ), V (H) = {(x 1, x 2,, x r ) 1 x i n i, i = 1, 2,, r}, n 1, n 2, n r r + 1 4, u H, (r + 1) - {u 1, u 2,, u r, u}, (r + 1) - {v 1, v 2,, v r, v}. 4.1. v 0, v 1,, v r G r + 1. H i = G N (v i ) = HP K(n 1, n 2,, n r ), i = 0, 1,, r. G 1 =< H 0 H 1 H 2 H r >, G 1 G G H 0, H 1,, H r,, v i / H i, v i H j, i, j = 0, 1, 2,, r, i j. N (v i ) V (H i ) = φ, i = 0, 1, 2,, r, H i = H i N (v i ) G 1 N (v i ) G N (v i ) = H i, i = 0, 1, 2,, r, H i = G 1 N (v i ) = G 1 N G 1 (v i ), i = 0, 1, 2,, r. G 1 = HP K(n1 +1, n 2 +1,, n r +1), G 1 N (v i ) = H i = HP K(n1, n 2,, n r ), N G 1 (v 0 ) = N H 1 (v 0 ) (N H 2 (v 0 ) N H 2 (v 1 )) (N H k (v 0 ) N H k (v 1 ) N H k (v k 1 )) (N H r (v 0 ) N H r (v 1 ) N H r (v r 1 )) (N G 1 (v 0 ) N G 1 (v 1 ) N G 1 (v r ))
No. 4 : 841 NG 1 (v 0 ) NG 1 (v 1 ) NG 1 (v r ) = V (G 1 ) N (v 0 ) N (v 1 ) N (v r ) r = (V (H i )) (N (v 0 ) N (v r )) = φ, 3.4 3.5 i=0 ν(g 1 ) = (n 1 + 1)(n 2 + 1) (n r + 1). G 1 = G, 3.2, G HP K(n 1, n 2,, n r ) -. G 1 G, N (v 0 ) N (v 1 ) N (v r ) = W, W φ G 1 = G W, V (G 1 ) W = φ, V (G 1 ) V (G) W. x V (G) W, x / W, x / N (v i ), i, x G N (v i ) = H i G 1, V (G) W V (G 1 ), G 1 = G W, G 1 HP K(n 1, n 2,, n r ) -. x G 1 w W. x H 0, x w W. H 0 = G N (v 0 ), {v 1, v 2,, v r } V (H 0 ), v H 0 {v 1, v 2,, v r, v} H 0 (r + 1) -, v w W,, v w W, H = G N (v) = HP K(n 1, n 2,, n r ) {v 0, v 1,, v r } V (H) H (r + 1) -, w H, w N H (v 0) N H (v 1) N H (v r) φ, 3.2, W N (v). n 1, n 2,, n r r + 2 5, u, v H 0, {v 1, v 2,, v r, u, v} V (H) (r + 2) -, W N (u) N (v). {v 1, v 2, v 3, v 4, u, v} (r + 2) -, H 0 {v 1, v 2,, v r, u, v}. W N (v 1) N (v 2), 3.1 x H 0, x G 1, x w W, G 1 N G 1 (x) = (G W ) N G 1 (x) = G (W N G 1 (x)) = G N (x) = HP K(n 1, n 2,, n r ), x G 1. G 1 HP K(n 1, n 2,, n r ) -. ν(g) = (n 1 +1)(n 2 +1) (n r +1), 3.2, G = HP K(n 1 + 1, n 2 + 1,, n r + 1). w W, V (G 1 ) N (w). < W >= F, G = G 1 + F G N (w) = G (N F (w) V (G 1 )) = G V (G 1 ) N F (w) = F N F (w) = HP K(n 1, n 2,, n r ), w W, F HP K(n 1, n 2,, n r ) -, F, G 2 F, G 2 = HP K(n1 + 1, n 2 + 1,, n r + 1), F = G 2 + F 1, F 1 = F V (G 2 ). G, G = G 1 + G 2 + + G k, G i = HP K(n1 + 1, n 2 + 1,, n r + 1), i = 1, 2,, k.
842 Vol. 37 5 5.1 5.2. 5.1 G = (V, E), {v 0, v 1,, v r } G V (G) G (k + 1) -, N (v 1 ) N (v 2 ) N (v k ) = (NF (v 1 ) NF (v 2 ) NF (v k )) (N (v 1 ) N (v 2 ) N (v k ) N (v 0 )), F = G N (v 0 ). 5.2 G = (V, E), u 1, u 2,, u k G, {v 0, v 1,, v r } V (G) G (r + 1) -, v i u j. F i = G N (v i ), i = 1, 2,, l, N (u 1 ) N (u 2 ) N (u k ) = (N F 1 (u 1 ) N F 1 (u 2 ) N F 1 (u k )) (N F 2 (u 1 ) N F 2 (u 2 ) N F 2 (u k ) N F 2 (v 1 )) (N F l (u 1 ) N F l (u 2 ) N F l (u k ) N F l (v 1 ) N F l (v l 1 )) N (u 1 ) N (u 2 ) N (u k ) N (v 1 ) N (v l ). m. 5.3 G HP K(n 1, n 2,, n r ) -, H = HP K(n 1 + 1, n 2 + 1,, n r + 1), n 1, n 2,, n r r 3. {v 1, v 2,, v k } V (G) {u 1, u 2,, u k } V (H) G H k -, N G(v 1 ) N G(v 2 ) N G(v k ) N H(u 1 ) N H(u 2 ) N H(u k ). k r + 1, 3.3 N H(u 1 ) N H(u 2 ) N H(u k ) = φ,. 1 k r, v G u H, {v 1, v 2,, v k, v} {u 1, u 2,, u k, u} G H (k + 1) -. G 1 = G N (v), H 1 = H N (u), G 1 = H1 = HP K(n1, n 2,, n r ), {v 1, v 2,, v k } V (G 1 ) {u 1, u 2,, u k } V (H 1 ) G 1 H 1 k -, NG(v 1 ) NG(v 2 ) NG(v k ) = NG 1 (v 1 ) NG 1 (v 2 ) NG 1 (v k ) + NG(v 1 ) NG(v k ) NG(v), NH(u 1 ) NH(u 2 ) NH(u k ) = NH 1 (u 1 ) NH 1 (u 2 ) NH 1 (u k ) + NH(u 1 ) NH(u k ) NH(u). G 1 = H1 = HP K(n1, n 2,, n r ), 3.4 N G 1 (v 1 ) N G 1 (v k ) = N H 1 (u 1 ) N H 1 (u k ), k r + 1,k = r, r 1,, 3, 2, 1..
No. 4 : 843 5.4 G 2 HP K(n 1, n 2,, n r ) -, H = HP K(n 1 +2, n 2 + 2,, n r + 2), n 1, n 2,, n r r 3 {v 1, v 2,, v k } V (G) {u 1, u 2,, u k } V (H) G H k -, N G(v 1 ) N G(v 2 ) N G(v k ) N H(v 1 ) N H(v 2 ) N H(v k ). 3.3, k r + 1, 1 k r, 5.3, G H v G, u H, G 1 = G N (v), H 1 = H N (u), {v 1, v 2,, v k } V (G 1 ) {u 1, u 2,, u k } V (H 1 ). G 1 HP K(n 1, n 2,, n r ) -, H 1 = HP K(n 1 + 1, n 2 + 1,, n r + 1), k r + 1, k = r, r 1,, 3, 2, 1. 5.5 G m HP K(n 1, n 2,, n r ) -, H = HP K(n 1 + m, n 2 + m,, n r + m), n 1, n 2,, n r r 3, {v 1, v 2,, v r } V (G) {u 1, u 2,, u k } V (H) G H k -, NG (v 1) NG (v k) NH (u 1) NH (u k). m = 1, 2, 5.3 5.4. m, m 1, 3.3 k r + 1,, 5.3, 5.4, m, k r + 1, k = r, r 1,, 3, 2, 1. 5.1 G m HP K(n 1, n 2,, n r ) -, n 1, n 2,, n r r 3, ν(g) (n 1 + m)(n 2 + m) (n r + m). m = 1, 3.1,., m 1 1, m, G m HP K(n 1, n 2,, n r ) -, H = HP K(n 1 + m, n 2 + m,, n r + m). 5.4, NG (v) N H (u), G H v G, u H. G 1 = G N (v), H 1 = H N (u), G 1 (m 1) HP K(n 1, n 2,, n r ) -, H 1 = HP K(n 1 + m 1, n 2 + m 1,, n r + m 1). ν(g) = ν(g 1 ) + N G(v) ν(h 1 ) + N H(u) = ν(h) = (n 1 + m)(n 2 + m) (n r + m). 5.2 G m HP K(n 1, n 2,, n r ) -, n 1, n 2,, n r r 3, ν(g) = (n 1 + m)(n 2 + m) (n r + m), G = HP K(n 1 + m, n 2 + m,, n r + m). G m HP K(n 1, n 2,, n r ) -, H = HP K(n 1 + m, n 2 + m,, n r + m), n 1, n 2,, n r r 3, ν(g) = ν(h). m = 1, 3.2, G = HP K(n 1 + 1, n 2 +1,, n r +1)., m 1 1. m, v G u H, G 1 = G N (v) (m 1) HP K(n 1, n 2,, n r ) -, H 1 = H N (u) = HP K(n 1 + m 1,, n r + m 1). 5.5 5.1, N G(v) N H(u) = ν(h) ν(h 1 ), ν(g 1 ν(h 1 ), ν(g 1 ) = ν(g) N G(v) ν(g) N H(u) = ν(h) N H(u) = ν(h 1 ), ν(g 1 ) = ν(h 1 ) = (n 1 + m 1)(n 2 + m 1) (n r + m 1), G 1 (m 1) HP K(n 1, n 2,, n r ) -. G 1 = HP K(n 1 + m 1, n 2 + m 1,, n r + m 1). v G, 2.2, G
844 Vol. 37 HP K(n 1 + m 1, n 2 + m 1,, n r + m 1) -, n i = n i + m 1 n i r 3, i = 1, 2,, r, 3.2 G = HP K(n 1 + m, n 2 + m,, n r + m).. [1] Erdös P, Harary F, Klawe M. Residually-complete graphs[j]. Ann. Disc. Math., 1980, 6: 117 123. [2],. [J]., 2011, 34(5): 778 785. [3] Liao J, Yang S, Deng Y. On connected 2 K n-residual graphs[j]. Mediterranean J. Math., 2012, 6: 12 27. [4],,. K n - [J]., 2014, 18: 59 68. [5] Liao J, Long G, Li M. Erdös conjecture on connected residual graphs[j]. J. Comput., 2012, 7: 1497 1502. [6] Michael Holu sa. Image segmentation using iterated graph cuts with residual graph[j]. Eduard Sojka Adv. Vis. Comput., 2013, 1: 228 237. [7] Trotta B. Residual properties of simple graphs[j]. Bull. Austr. Math. Soc., 2010, 82: 488 504. [8],,. m HP K(n 1, n 2, n 3, n 4 ) - [J]., 2014, 34(2): 324 334. [9] Duan H. On connected m multiply 2 dimensions composite hyperplanne complete graph s residual graphs[j]. J. Discrete Math. Sci. Crytography, 2014, 16: 313 328. [10] Yang H S. The isomorphic factorization of complete tripartite graphs K(m, n, s) a proof of F. Harary, R. W. Robinson and N. C. Wormald s conjecture[j]. Disc. Math., 1995, 145(1-3): 239 257. [11] Liang Z, Zuo H. On the gracefulness of the graph[j]. Appl. Anal. Discrete Math., 2010, 10: 175 180. MULTIPLY HYPERPLANE COMPLETE RESIDUAL GRAPH DUAN Hui-ming 1, SHAO Kai-liang 1, ZHANG Qing-hua 1, ZENG Bo 2 (1.College of Science, Chongqing University of Posts and Telecommunications, Chongqing 400065, China) (2.School of Business Planning, Chongqing Technology and Business University, Chongqing 400067, China) Abstract: In this paper, we study any number of dimensions hyperplane complete residual graphs and multiply any number of dimensions hyperplane complete residual graphs, and extend Erdös, Harary and Klawe s definition of plane complete residual graph to hyperplane and obtain dimensions hyperplane complete residual graph. With the method of including excluding principle and set operation, we obtain the minimum order of any number of dimensions hyperplane complete residual graphs and a unique minimal any number of dimensions hyperplane complete residual graph, and an important property of any number of dimensions hyperplane complete residual graph. In addition, we obtain the minimum order of multiply any number of dimensions hyperplane complete residual graphs and a unique minimal multiply any number of dimensions hyperplane complete-residual graphs. Keywords: residually graph; close neighborhood; isomorphic; independent set 2010 MR Subject Classification: 05C35; 05C60; 05C75