Kronecker乘积图超连通性（英文）AbstractLet G1 and G2 be two connected graphs.The Kronecker product G1XG2 is the graph with vertex set V (G1 XG2) = V (G1) XV (G2) and the edge set E (G1XG2)= (ul, vl) (u2, v2): ulu2WE (Gl),vlv2E (G2) . In this note, we show that GXKn (n$4) is super- k if and only if k (G) n 6 (G) (n? 1), where G is any connected graph and Kn is the complete of n vertices. Furthermore, we show that for any connected graph G with at least three vertices, ifk (G)= 6(G ) then GXKn is super- k for n23. This resuIt strengthens the known results of Guo et al.Key wordsKronecker product； Connectivity； Super connectivityCLC numberO 15Document codeAlintroductionThere have been several proposals for measures of stability of a communication network. Thefirst such parameters one generally encounters are connectivity and edge connectivity, which measure the vulnerability of a graph or network The connectivity gives the minimum cost to disrupt the networkAll graphs considered in this paper arefinite， simple and connected. For notation and terminology not defined here, we refer to West1. The connectivity of a simple graph G is the number, denoted by k (G), equal to the fewest number of vertices whose removal from G resu Its in a disconnec ted or an isola ted ver tex. A set S? V (G) is a vertex-cut of G, if G? S is either disconnected or an isolated vertex. In particular, a vertex-cut S is called t rivial if G? S isolates a ver tex. A graph G is super cormected, or simply super- k , if every minimum vertexcut of G is trivial, i. e. every minimum vertex-cut of G isolates a ver tex. For a graph G, we denote by 5 (G) the minimum degree of G, d(v) the degree of the vertex v, N (v) the set of the neighbors of v.The Kronecker product G1XG2of graphs Gland G2is the graph with the vertex set V (Gl) XV (G2), in which two vertex (ul, vl) and (u2, v2) are adjace nt if and only if ulu2(Gl) and vlv2WE (G2) . Hence, it is clear that the degree of a vertex(u, v) in Gl XG2is equal to dGl (u) dG2 (v)Weichsel2proved that if Gland G2are two connected graphs, then G1 XG2is connected if and only if Gland G2are not both bipartite graphs Although there are many papers on the Kronecker product (sometimes called direct product, tensor product , cross product, categorical product, or conjunction etc. ) of graphs, very few resuIts on the connectivity of the Kronecker product of graphs have been reported. Bre sar and Spacapan3obtained some bounds on the edge-connectivity of Kronecker products of graphs, and upper bounds on the connectivity of the Kronecker products of graphs Mamut and Vumar4showed thatk (KnXKm) = (n? 1) X (m? 1) for any nm2 and n3； Guji and Vumar5investigated the connectivity of the Kronecker product of a connected bipartite graph G and complete graph Knwith n三3 and reported that k (GXKn) =minn k (G), (n? 1) 5 (G) ； Later, L. Guo et al. 6 strengthened their result by showing that for any connected bipartite graph G and complete graph Knwith n3, if k (G) = 5 (G), then GXKnis super- k . Very recently, Y. Wang and B. Wu7proved that k (GXKn) =minn k (G), (n? 1) 5 (G) for any connected graph G and complete graph Knwith n3 In this paper, we show that GXKn (n$4) is super- k if and only if n k(G) 8 (G) (n? 1) . Furthermore, we show that forany connected graphs G, if k (G) = 6 (G) then GXKnis super- k for n3We show claim 1 bycontradiction. Assume that there exist integers k , 1 1，t and i 1,m, such that V (Hk) ASi? =? and V (Hl) Cl Si ? =? . Take a vertex (xi, a) eV (Hk) ASiand (xi, b) eV (Hl) GSi. Since S is non-trivial, there exist two vertices, say (xj, c) in V (Hk) and (xg, d) GV (Hl) such that (xi, a) (xj, c) in E (Hk) and (xg, d) (xi, b) WE (Hl)(g may equal to j) Note that Hkis not connected to Hlin H? S, then we have a = d and c = b. In the following, we will show that Hland Hkare connected by at least 5(G) (n? 1)+1 internally vertex-disjoint pathsFor simplicity, we use 5 for 5 (G) Let T 二ul, u2, . . . , u ? NG (xi) . We consider the subgraph F = GT of G induced by T. Take a maximum matching M of F. Let q = |M| and M = ulu2, u3u4, ,u2q? Iu2q, without loss of generality There are 6 (n? 2) Type-I paths , 2q Type-II paths and n ? 2 Type-III paths connecting Hland Hkas defined in the following.Type-I pa ths： for any pE 1, 2,， 6 , and any yWV (Kn) a, b,Ppy： (xi, a) (up, y) (xi, b)1 D B West. Introduction to Graph Theory. Second Edition, Prentice Hall, Upper Saddle River, NJ, 2001.2 P M Weichese 1. The Kornecher product of graphsProc Amer Math Soc, 1962,13：47-52.3 B Bre、 sar, S 7 Spacapan. On the Connectivityof the direct product of graphs Australas J Combin, 2008,41：45-56._4 A Mamut， E Vumar. Vertex vulnerability parameters of Kronecker product of complete graphs Inform Process Lett, 2008,106：258-262.5 R Guji, E Vumar. A note on the connectivityof Kronecker products of graphs