ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 8 (2015) 235-244
Super connectivity of direct product of graphs*
Jin-Xin Zhou
Department of Mathematics, Beijing Jiaotong University, Beijing 100044, P.R. China
Received 15 July 2012, accepted 14 June 2014, published online 23 January 2015
For a graph G, k(G) denotes its connectivity. A graph G is super connected, or simply super-K, if every minimum separating set is the neighborhood of a vertex of G, that is, every minimum separating set isolates a vertex. The direct product Gi x G2 of two graphs Gi and G2 is a graph with vertex set V(Gi x G2) = V(Gi) x V(G2) and edge set E(Gi x G2) = {(ui, vi)(u2, v2) | uiu2 € E(Gi),viv2 € E(G2)}. Let r = G x Kn, where G is a non-trivial graph and Kn(n > 3) is a complete graph on n vertices. In this paper, we show that r is not super-K if and only if either K(r) = nK(G), or r = K^ x K3(^ > 0).
Keywords: Super connectivity, direct product, vertex-cut. Math. Subj. Class.: 05C40, 05C76
1 Introduction
Throughout this paper only undirected simple connected graphs without loops and multiple edges are considered. Unless stated otherwise, we follow Bondy and Murty [4] for terminology and definitions.
Let G = (V(G),E(G)) be a graph. For two vertices u,v G V(G), u ~ v means that u is adjacent to v and uv is the edge incident to u and v in G. The set of vertices adjacent to the vertex v is called the neighborhood of v and denoted by NG(v), i.e., NG(v) = {u | uv G E(G)}. The degree of v is equal to |NG(v)|, denoted by dG(v). The number ¿(G) = min{dG(v) | v G V(G)} is the minimum degree of G. For a subset S C V(G), the subgraph induced by S is denoted by G[S]. As usual, Km,m, (m is a positive integer) denotes the complete bipartite graph; Km,m - mK2 denotes the graph obtained by removing a 1-factor from Km,m; Kn denotes the complete graph on n vertices; and Zn denotes the ring of integers modulo n.
*This work was supported by the National Natural Science Foundation of China (11271012).
E-mail address: jxzhou@bjtu.edu.cn (Jin-Xin Zhou)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
236
ArsMath. Contemp. 8(2015)235-244
A separating set of a graph G is a set of vertices whose deletion either disconnects G or reduces G to the trivial graph K^ The connectivity of the graph G is the minimum number of vertices in a separating set of G, and will be denoted by k(G). In particular, k(K„) = n - 1, and k(G) =0 if and only if G is disconnected or a K1. Clearly, k(G) < ¿(G). A graph G with minimum degree ¿(G) is maximally connected if ¿(G) = k(G).
An interconnection network is often modeled as a graph G, where V(G) is the set of processors and E(G) is the set of communication links in the network. The connectivity k(G) of G is an important measurement for fault-tolerance of the network, and the larger k(G) is, the more reliable the network is. As more refined indices of reliability than connectivity, super connectivity was proposed in [2, 3]. A graph G is super connected, super-k, for short if every minimum separating set isolates a vertex of G.
The direct product G1 x G2 of two graphs G1 and G2 is defined as the graph with vertex set V(G1) x V(G2) and edge set {(u1, v1)(u2, v2) | u1u2 e E(G1),v1 v2 e E(G2)}. The direct product is also called the Kronecker product, tensor product, cross product, categorical product, or conjunction. As an operation on binary relations, the direct product was introduced by Whitehead and Russell in their Principia Mathematica [21]. It is also equivalent to the direct product of the adjacency matrices of the graphs (see [20]). As one of the four standard graph products [11], the direct product has been studied from several points of view (see, for example, [1, 6, 8, 12, 13, 15]).
The connectivity of the direct product of graphs has also been investigated in several recent publications. For example, Bresar and Spacapan [7] obtained an upper bound and a lower bound on the edge-connectivity of the direct products with some exceptions, and they also obtained several upper bounds on the vertex-connectivity of the direct products of graphs. Mamut and Vumar [14] proved that K(Km x Kn) = (m - 1)(n - 1) where m > n > 2. In [9], it was shown that if n > 3 and G is a bipartite graph, then k(G x Kn) = min{nK(G), (n - 1^(G)}, and furthermore, the authors also conjectured that this is true for all nontrivial graph G. Later, this conjecture was confirmed independently by Wang and Wu [17] and Wang and Xue [18].
More recently, several papers dealing with the super-connectivity of direct product of graphs were published. Guo et al. [10] showed that for a bipartite graph G with k(G) = ¿(G), G x Kn(n > 3) is super-K. In [19], the authors generalized this result by showing that for a nonbipartite graph G with k(G) = ¿(G), G x Kn(n > 3) is super-K. In [19], the authors also pointed out that Guo et al.'s result is not true when G =	> 1) and
n = 3, and they also claimed that except for this case, Guo et al.'s statement is true.
The aim of this article is to determine all graphs G such that G x Kn(n > 3) is not super-K. The following is the main result.
Theorem 1.1. Let r = G x Kn, where n > 3 and G is a non-trivial graph. Then r is not super-K if and only if one of the following happens.
(1)	G has a minimum separating set T so that T x V(Kn) is a minimum separating set of r. In particular, K(r) = nK(G).
(2)	r = Ke/ x Ks(* > 0).
From Theorem 1.1 we can immediately obtain the following corollaries.
Corollary 1.2. [17, 18] Let r = G x Kn, where n > 3 and G is a non-trivial graph. Then
K(r) = min{nK(G), (n - 1^(G)}.
Jin-Xin Zhou: Super connectivity of direct product of graphs
237
Corollary 1.3. [10, 19] For a maximally connected graph G, G x K„(n > 3) is not super-K if and only if n = 3 and G =	> 0).
2 Proof of Theorem 1.1
We start by introducing some notations. Notations.
•	r := G x K„, where n > 3 and G is a non-trivial graph.
•	V(G) := {ui | i e Zm|.
•	V(K„) := Z„.
•	Vi := {ui| x V(K„), i e Zm.
•	S: a minimum separating set of r.
•	r - S := Uri, where each r is a connected component of r - S.
•	Wi := V(ri).
In the following Lemmas 2.1-2.5, we assume that r is not super connected, and S is a minimum separating set of r with each component ri of r - S having at least two vertices. By the definition, we can obtain the following easy facts.
Lemma 2.1. (1) J(r) = (n - 1)J(G).
(2)	For any i e Zm, Vi is an independent subset of V(r).
(3)	If ui0 is adjacent to vil in G, then (ui0, j) ~ (uil, k)(in r) if and only if j = k. In particular, r[Vi0 U Vil ] = K„,„ - nK2.
(4)	Let T be a separating set of G. Then T x V(K„) is also a separating set of r. In particular, |S| = K(r) < min{nK(G), (n - 1)J(G)|.
(5)	s > 2 and |Wi| > 2 for each i e Zs.
Lemma 2.2. For each (ui, j) e S, (ui, j) has at least one neighbor in Wi for each i e Zs.
Proof. Suppose to the contrary that (ui, j) has no neighbors in Wi for some i e Zs. Set S' = S - {(ui, j)|. Then Wi must be a component of r - S'. This implies that S' is also a separating set of r, contrary to the minimality of S.	□
Lemma 2.3. For two components Wk, W^, if there exist (ui, i') e Wk and (uj, j') e W^ such that ui ~ uj (in G), then i' = j' and Wk n Vi = {(ui, i')| and We n Vj = {(uj, j')|.
Proof. Since ui ~ uj (in G), it follows from Lemma 2.1 (3)that r[V U Vj ] = K„,„ - nK2. As r - S is disconnected, there are no edges between Wk and W^. Consequently, i' = j'
and Wk n Vi = {(ui, i')| and W£ n Vj = {(u, j')|.	□
Lemma 2.4. Assume that for each Vi there exists at most one Wj such that Vi n Wj = 0. Then S = T x V(K„), where T is a minimum separating set of G. In particular, K(r) = nK(G).
238
Ars Math. Contemp. 8 (2015) 235-244
Proof. We shall first show the following two claims.
Claim 1 If there exists an i e Zm such that Vj n S = 0 and Vj C S, then | Vi n S| = n - 1. Furthermore, for each Wj, there is a V such that |Wj n V«| = 1.
By the assumption, there is a unique j e Zs such that Vj n Wj = 0. By Lemma 2.2, for each vertex, say («j, i'), in V n S, there is at least one neighbor, say (««, ¿"), in each Wt with t = j. By Lemma 2.3, | Vj n Wj | = |V« n Wt| = 1. From our assumption we know
that |Vj n S| = |V« n S| = n - 1.
Claim 2 For each i e Zm, either Vj n S = 0 or Vj C S.
Suppose on the contrary that there exists an i e Zm such that Vj n S = 0 and Vj C S. For each j e Zs, let % = e Zm | |V« n Wj| = 1}, and set nj = |. By Claim 1, nj > 0. Without loss of generality, assume that n0 < ni < ... < ns_i.
Assume that W0 C |J«eno V«. Then for each (uj, e W0, we have |Vj n W0| = 1. Combining this with Lemma 2.3, we have for a fixed (uj, e W0, if — uj(in G), then | Vk n S| > n - 1. As n > 3, one has
|S| > |Vj n S| + ^ |V n S| > n - 1 + ¿(G)(n - 1) >K(r).
Uj eNa(ui)
A contradiction occurs.
Now assume that Wo % LUq0. Let U = |JVj, Zo = LUq0 V, and Zi = U«eni V«. Set T = U U Z0. Clearly, |Z0 n W0| = n0. Since n1 > n0 and n > 3, one has
|Z0 nWo| = n0 < n1(n - 1) = |Z1 n S|. Then
|T | = |U | + |Zo| = |U | + |Zo n s | + |Zo n Wo|
<	|U| + |Zo n S| + |Zi n S|
<	|S|.
Since S is a minimum separating set, r - T is connected. So there is an edge between Wo \ T and V(r) \ (T U Wo). We may assume that (vj, j) e Wo \ T is adjacent to (vs,k) e V(r) \ (T U Wo). Obviously, (vs,k) e S \ T. Since U = |JVQS Vj and T = U UZo, one has Vs % S. If Vs nWo = 0, then by Claim 1, we must have |VsnWo| = 1 and so Vs C Zo C T. This contradicts the fact that (vs, k) e S \ T. Consequently, Vs n Wo = 0. It follows that V n Wt = 0 for some t > 0. Since (vj, j) - (vs, k), by Lemma 2.3, |Vj n Wo| = 1 and so Vj C Zo C T. This contradicts the fact that (vj, j) e Wo \ T.
Now we are ready to finish the proof. From Claim 2 it follows that S = T x V (Kn) for some subset T of V(G). Since n > 3, T is a separating set of G (see [20]). So, |S| > K(G)n. However, by Lemma 2.1 (4), |S| < n«(G). Hence, |S| = n«(G).	□
Lemma 2.5. Assume that there exist a Vj and two different Wj0, Wj such that Vj n Wk = 0 with k = jo, ji Then n = 3 and G =	> 0).
Proof. Recall that Wk = V(rk) with k = jo or j^ We shall finish the proof by the following claims.
Claim 1 V(r) = Wj0 U Wjl U S, | Vj n Wj01 = |Vj n Wjl | = 1 and | Vj n S| = n - 2.
Jin-Xin Zhou: Super connectivity of direct product of graphs
239
By Lemma 2.1 (2), Vj is an independent subset, and by Lemma 2.1 (5), |Wk | > 2 with k = j0 or ji. It follows that Vj n Wk c Wk. Since j is connected, there exist
(ui,to) € Vi n Wjo and («¿o,¿0) € Wjo \ (V n Wjo) such that («¿,¿0) - («¿o,¿0). Similarly, there exist (ui,i1) € Vi n Wj, and (u^, tj) € Wj \ (Vi n Wj,) such that (ui,t1) — (w^ ,ti). From Lemma 2.3 we obtain that ¿0 = t1, V n Wjo = {(ui,i0)} and Vio n Wjo = {1 («¿o,ti)}, andtj = ¿0, Vi n Wj = {(«¿,¿1)} and V^ nW,^ = {(u^,¿0)} (see Figure 1). In particular, we have |Vi n Wjo | = |Vj n W, | = 1.
Figure 1: Explanation of the proof of Claim 1
It follows that | Vi n S| < n - 2. If |Vi n S| < n - 2, then we would have Vi n Wj = 0 for some j = jo, ji. Take (ui,i) € Vi n Wj. Clearly, t = io,ti. This forces that (ui, t) — (ui0, t1), contrary to the fact that j and rj are two distinct components. Thus,
|Vi n S| = n - 2.
At last, we shall show that s = 2. Suppose to the contrary that s > 2. Since | Vi n S| =
n - 2 > 0, we can take (ui, j) € Vj n S. By Lemma 2.2, (ui, j) has a neighbor, say (uk, j') in each Wj with j = jo, ji. Since to = ti, either (ufc, j') - («i,to) or (ufc, j') - («i,ti). This is again contrary to the fact that j, j and rj are three distinct components. Thus, s = 2 and hence V(r) = Wj0 U Wj U S.
By Claim 1, we may assume that Vj n Wj0 = {(ui, to)} and Vj n Wj = {(ui, ti)}.
Claim 2 For each (w^-, € Nr((ui,to)) n Wj0, |Vj n S| = n - 1 or n - 2. There is at least one (ui0,40 € Nr((wi,to)) n Wj0 such that |Vi0 n S| = n - 2.
Take («€ Nr((«i,to)) n Wj0. From Claim 1 we see that Vi n Wj, = {(«i,ti)}. By Lemma 2.3, we have | Vj n Wj01 = 1, implying | Vj n S| < n - 1. If |Vj n S| < n - 1 then we must have Vj- n Wj, = 0. By Claim 1, we have |Vj n S| = n - 2. Therefore, IV n S| = n - 1 or n - 2.
Suppose that for each («j, € Nr ((ui, to)) n Wj0, we have | Vj n S | = n - 1. Noting that n > 3, one has
|S| > |Vi n SI + ^ IUj- n S| > n - 2 + J(G)(n - 1) >K(r),
Uj eNa(ui)
a contradiction. Thus, there is at least one (ui0,40 € Nr ((ui, to)) n Wj0 such that |Vi0 n S| = n - 2. 0 0 0
Now we know that Claim 2 holds. Since (ui0,4) € Nr((wi,to)) n Wj0, it follows from Lemma 2.3 that Vi0 n Wj0 = {(ui0, ti)} and Vi0 n Wj, = {(ui0, to)} (see Figure 2). By the arbitrariness of Vi, Claims 1,2 also hold if we replace Vi by Vi0.
240
Ars Math. Contemp. 8 (2015) 235-244
Figure 2: Explanation of Claims 1,2
For the convenience of statement, we shall use the following notations in the remainder of the proof.
Notations
(1) (2)
(3)
(4)
(5)
(6)
Ni = Nr((ui,to)) n Wj0, Ni0 = Nr((uio,ti)) n Wjo,
= {k G Zm | Vk n Ni = 0}, Oio = {k G Zm | Vk n Nio = 0},
| k G a,Vk n Nr((ui,to))= 0}, | k G ^io,Vk n Nr((uio,ti)) = 0}.
Ai = {k G Zm Aio = {k G Z.
It is easy to see that NG(wi) = {uk | k G ^ U Ai} and NG(uio) = {uk | k G U Aio}. Hence, + |Ai| = dG("i) and | + |Aio| = dG(uio).
Claim 3 |Ni| = |a| and N| = K|.
By Claim 1, for each k G we have |Vfc n Wjo | = 1. It follows that |Ni| = Similarly, N | = ^o |.
Claim 4 Both Ni and Nio are independent subsets of V(r).
Take any two vertices, say (ui1, t), (ui2, t') in Ni. Since V n Wj = {(ui, ti)}, from Lemma 2.3 it follows that t = t' = t1. So, (ui1, t) is not adjacent to (ui2, t'). Therefore, Ni is an independent subset of V(r). Similarly, Nio is also an independent subset.
Claim 5 (U
keQiUAi
Vk ) n (U^q Vk)= 0 and (U
k£Qin UAj.
Vk) n (U^Qi Vk) = 0.
Suppose that (UkeaUA, Vfc) n (Ufcen Vfc) = 0. Take (u.,t) G (U
keQiUA,
Vk) n
(Ufce^0 Vfc). Then VjnNio = 0, implying that Vj nWjo = 0. Assume (uj,t') G VjnWjo. Clearly, ui and uio are neighbors of uj in G. Since t0 = t1, either (uj ,t') ~ (ui ,t1) or (uj, t') ~ (uio, t0). This is contrary to the fact that there are no edges between Wjo and Wji. Thus, (Uke^iUAi Vk) n (Ufc£Qio Vk) = 0. Similarly, we have (UkeQ,oua,o Vk) n (Uken, Vk)= 0.
Claim 6 Let k G Ai U Ai o. Then Vk n Wjo = 0 and |Vk n S| > n - 1.
Assume k G A^ Then uk G NG(u^. If Vk n Wj0 = 0, then take (uk, t) G Vk n W.
J o •
Since k G ^i, (uk, t) is not adjacent to (uj, to), and hence t = to. Consequently, (uk, t) (uj, ii), a contradiction. Thus, Vk n Wj0 = 0. By Lemma 2.3, |Vk n W. | < 1, and hence | Vk n S | > n -1. With a similar argument, we can show that if k G Ai0, then Vk n Wj0 = 0 and |Vk n S| > n - 1.
Jin-Xin Zhou: Super connectivity of direct product of graphs
241
Claim 7 (1) n = 3; (2) |N,| = |Nio | = ¿(G); (3) |A,| = |Aio | = 0; (4) |S| = 25(G); (5) S = U fceniun^0 (Vk nS); (6) for each k e Q, UQ,o, |Vk nS | = |Vk nWj | = V nWj | = 1.
By the arbitrariness of V, and Vi0, we may assume that |Ni | < |Ni01. By Claim 5,
|S| > | J (Vfc n S)| + |( J (Vfc n S))|.	(2.1)
kefiio	fcefiiUAi
By Claim 2, if k e Q, U Qjo, then |Vk n S| > n - 2, and by Claim 6, if k e A, U Aio, then | Vfc n S| > n - 1. It follows that
|S| > (n - 2)|Oio| + (n - 2)|Q,| + (n - 1)|A,|.	(2.2)
By Claim 3, we have
|S| > (n - 2)|Nio| + (n - 2)|N,| + (n - 1)|A,|.	(2.3)
Since |Nio | > | and n > 3, we obtain that
|S| > 2(n - 2)|Ni| + (n - 1)|A,| > (n - 1)dG(Ui).	(2.4)
However, by Lemma 2.1 (4), we have | S | < (n -1) 5( G). So, in the above four inequalities, "=" must hold. By Eq. (2.4) we obtain that n = 3, |N,| = |N,o |, and 5(G) = dG("i). Furthermore, for each k e Q, UQio, |Vk nS| = n-1, and for each k e A,, |Vk nS | = n-1. It follows that
|S | = 2|N,| + 21 A, | = 25(G).	(2.5)
To show that | A, | = | A,o | = 0, we shall first show that
( J Vfc) n ( J Vfc) = 0.
keAi	kefiio UAio
Suppose on the contrary that for some k e A,, Vk n(U kefi. uA Vk) = 0. Since |Vk nS| = n - 1, from Claim 6 it follows that |Vk n W^ | = 1. Take (uk ,t) e Vk n W^. Then «,, «,o are neighbors of uk in G. Since t0 = ti, either (uk,t) ~ («¿,¿1) or (uk,t) ~ (uio, t0). This is contrary to the fact that there are no edges between W0 and W1. Thus,
(UkeAi Vk) n (U^uA,o Vk) = 0. It follows that
|S| > | UkeniouAio (Vk n S)| + |(Uke^iUAi(Vk n S))|
= | Ukenio (Vk n S)| + |(Uke^iUAi(Vk n S))| + |(JkeAio (Vk n S)| > 2|N,| + 21 A, | +2|A,o | = 25(G)+ 2|A, o |.
Combining this with Eq. (2.5) we obtain that |A, o | = 0. Since dG(wi) = 5(G), we have dG(u, o) > dG(ui). Recall that |N,| + |A,| = dG(ui) and o | + |A,o | = dG(Mj o). Since |N,| = |N, o |, one has |A, o | > |A,|, implying |A,| = 0. At last, from Eq. (2.1) it can be deduced that
S = ( J (Vk n S)) u ( J (Vk n S)).	(2.6)
kefiio	kefii
242
Ars Math. Contemp. 8 (2015) 235-244
Claim 8 Wj0 = Nj U Nj0.
Suppose that Wj0 = N U Ni0. Since r0 is a component of r - S, we can take a vertex,
say (vkl, t), in W, - (N U Ni0 ) such that (vkl, t) is adjacent to some vertex, say (vk2, t'), in Nj U Nj0. Since (vfc2, t') U Nj0, by Claim 7 |Vfc2 n W, | = 1. By Lemma 2.3, we have |Vkl n Wj01 = 1. By Claim 1, we have Vkl n S = 0. From Eq. (2.6) we see that ki G Qi0 U Qj, and hence (vkl, t) G N U Ni0, a contradiction. Thus, Wj0 = N U Ni0.
Wj0	S	W,
Figure 3: Explanation of Claims 8,9
Claim 9 m = |G| = 2J(G).
By Claim 8, |Wj01 = 2J(G). So, m > |Wj01 = 2J(G). Suppose that m > 2J(G). By Claim 7, for each k G ft, U üio, |Vk n l| = |Vk n Wj01 = |Vk n 1 = 1, and
S = Ufc£Qi0 Ufi, (Vk n S). This implies that Ufc£Qi0 Ufi, (Vk n Wj1 ) is a proper subset of Wj1. By the connectedness of take an edge e in ri such that one end, say (ukl, t), of e is
in UfceQi Ufii (Vk n Wj1 ) and the other end, say (uk2 , t'\ is in Wj1 \UfceQi UQi (Vk n Wj1). By Claim 7, | Vk1 n Wj01 = 1, and by Lemma 2.3, we have | Vk2 n W^ | = 1. By Claim 1, |Vfc2 n S| > 1. It follows from Eq. (2.6) that k2 G fti0 U ft,. This forces that (ufc2 ,t') G Ufc£Qi0 Ufi, (Vk n Wj1 ), a contradiction.
Claim 10 G = K^, where i = ¿(G).
Clearly, {wfc | k G ft, U fti0} C V(G). By Claim 9, m = |G| = 2J(G). It follows that V(G) = {ufc | k G ft, U fti0}. Set Bo = {wfc | k G ft,} and Bi = {wfc | k G ft,0}. Take any two vertices, say uk1 and uk2, in B0. Suppose uk1 ~ uk2. By Claim 7, we may assume that Vki n Wj0 = {(wki, d,)} with i = 1 or 2. From Claim 4 we obtain that (uk1, d1) is not adjacent to (uk2, d2), and hence d1 = d2. Since uk1 ~ uk2, (uk1, d1) is adjacent to all the remaining vertices in Vk2. Again, by Claim 7, we get that |Vk2 n Wj | = 1. This implies that there is an edge between Wj0 and Wj, a contradiction. Therefore, uk1 and uk2 are nonadjacent. By the arbitrariness of uk1 and uk2, we get that B0 is an independent subset of V(G). Similarly, B1 is also an independent subset of V(G). It follows that G must be a bipartite graph with two partition sets B0 and B1. By Claims 3,7, we know that |Bo| = |B11 = ¿(G). This means that G ^ K^, where i = ¿(G).	□
Lemma 2.6. Let i be a positive integer. Then K^ x K3 is not super-K.
Proof. Let B0 = {v, | i G Z^} and B1 = {u, | i G Z^} be the two partition sets of K^. Set V(K3) = Z3. Let S = V(K^) x {1}. Clearly, |S| = 2i. By [9], k(K^ x K3) = 2i.
Set W0 = (B0 x {0}) U (b1 x {2}) and W1 = (B0 x {2}) U (B1 x'{0}). Clearly, V(K^ x K3) = S U W0 U W1. It is also easy to see that r[Wj] = K£j£ for i = 0,1.
Jin-Xin Zhou: Super connectivity of direct product of graphs
243
Furthermore, in K^ ( K3 there are no edges between W0 and Wi. It follows that K^ x K3 - S is disconnected with no isolated vertices. Therefore, K^ x K3 is not super-K. □
Proof of Theorem 1.1. By Lemmas 2.4 and 2.5, we can get the necessity. For the sufficiency, by Lemma 2.6, K^ x K3 is not super-K.
Now assume that k(T) = uk(G). Suppose to the contrary that r is super-K. Then K(r) = S(r) = (n - 1)S(G), and hence (n - 1 )S(G) = uk(G). So, k(G) < 5(G). Let T be a minimum separating set of G. Then G - T has no isolated vertices. By Lemma 2.1 (4), T x V(Kn) is a separating set of r. Clearly, |T x V(Kn)| = nK(G). So, T x V(Kn) is also a minimum separating set of G. Since r is super-K, T x V(Kn) must be the neighborhood of some vertex, say (ui,j). Let uk e T. Then (uk, j) € T x V(Kn), and hence (u, j) ~ (uk, j). This is clearly impossible by the definition of the direct product of graphs. Thus, r is not super-K.	□
Acknowledgements: The author is indebted to the anonymous referee for many valuable comments and constructive suggestions.
References
[1]	N. Alon and E. Lubetzky, Independent sets in tensor graph powers, J. Graph Theory 54 (2007), 73-87.
[2]	D. Bauer, F. Boesch, C. Suffel and R. Tindell, Connectivity extremal problems and the design of reliable probabilistic networks, in: The Theory and Application of Graphs, Wiley, New York, 1981, 45-54.
[3]	F.T. Boesch, Synthesis of reliable networks: A survey, IEEE Trans. Reliability 35 (1986), 240246.
[4]	J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Elsevier North Holland, New York, 1976.
[5]	A. Bottreou and Y. Metivier, Some remarks on the Kronecker product of graphs, Inform. Process. Lett. 68 (1998), 55-61.
[6]	B. Bresar, W. Imrich, S. KlavZar and B. Zmazek, Hypercubes as direct products, SIAM J. Discrete Math. 18 (2005), 778-786.
[7]	B. Bresar and S. Spacapan, On the connectivity of the direct product of graphs, Austral. J. Combin. 41 (2008), 45-56.
[8]	S.A. Ghozati, A finite automata approach to modeling the cross product of interconnection networks, Math. Comput. Model. 30 (1999), 185-200.
[9]	R. Guji and E. Vumar, A note on the connectivity of Kronecker product of graphs, Appl. Math. Lett. 22 (2009), 1360-3163.
244
Ars Math. Contemp. 8 (2015) 235-244
[10]	L. Guo, C. Qin and X. Guo, Super connectivity of Kronecker product of graphs, Inform. Process. Lett. 110 (2010), 659-661.
[11]	R. Hammack, W. Imrich and S. KlavZar, Handbook of Product Graphs, Second Edition, CRC Press 2011.
[12]	R.H. Lammprey and B.H. Barnes, Products of graphs and applications, Model. Simul. 5 (1974), 1119-1123.
[13]	J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos and Z. Gharamani, Kronecker graphs: an approach to modeling networks, J. Mach. Learn. Res. 11 (2010), 985-1042.
[14]	A. Mamut and E. Vumar, Vertex vulnerability parameters of Kronecker product of complete graphs, Inform. Process. Lett. 106 (2008), 258-262.
[15]	G. Mekis, Lower bounds for the domination number and the total domination number of direct product graphs, Discrete Math. 310 (2010), 3310-3317.
[16]	J. Nesetril, Representations of graphs by means of products and their complexity, in: Mathematical Foundations of Computer Science, in: Lecture Notes in Comput. Sci. 118, Springer, Berlin, 1981,94-02.
[17]	Y. Wang and B. Wu, Proof of a conjecture on connectivity of Kronecker product of graphs, Discrete Math 311 (2011), 2563-2565.
[18]	W. Wang and N.-N. Xue, Connectivity of direct products of graphs, arXiv: 1102.5180v1 [math.CO] 25 Feb 2011.
[19]	H. Wang, E. Shan and W. Wang, On the super connectivity of Kronecker product of graphs, Inform. Process. Lett. 112 (2012), 402-405.
[20]	P.M. Weichsel, The Kronecker product of graphs, Proc. Amer. Math. Soc. 8 (1962), 4-52.
[21]	A.N. Whitehead and B. Russell, Principia Mathematica, 2, Cambridge University Press. Cambridge, 1912, p.384.