1、1Kronecker 乘积图的超连通性(英文)AbstractLet G1 and G2 be two connected graphs. The Kronecker product G1G2 is the graph with vertex set V （G1G2） = V （G1）V （G2） and the edge set E（G1G2） = （u1，v1） （u2，v2） ： u1u2E（G1） ，v1v2E（G2）. In this note， we show that GKn （n4） is super-if and only if（G）n （G） （n？1） ， where G
2、 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， if（G） =（G） then GKn is super-for n3. This result strengthens the known results of Guo et al. Key wordsKronecker product； Connectivity； Super connectivity CL
3、C numberO 15Document codeA 1Introduction There 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
4、 minimum cost to disrupt the network. 2All 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（G） ， equal to the fewest number of vertices whose removal from
5、G results in a disconnected or an isolated vertex. 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 trivial if G？S isolates a vertex. A graph G is super connected， or simply super-， if every minimum vertex-cut of G is t
6、rivial， i.e. every minimum vertex-cut of G isolates a vertex. For a graph G， we denote by（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 G1G2of graphs G1and G2is the graph with the vertex set V （G1）V （G2） ， in which two vertex （
7、u1，v1） and （u2，v2） are adjacent if and only if u1u2E（G1） and v1v2E（G2）. Hence， it is clear that the degree of a vertex（u，v） in G1G2is equal to dG1（u）dG2（v）. Weichsel2proved that if G1and G2are two connected graphs， then G1G2is connected if and only if G1and G2are not both bipartite graphs. Although
8、there are many papers on the 3Kronecker product （sometimes called direct product， tensor product ， cross product， categorical product， or conjunction etc.） of graphs， very few results on the connectivity of the Kronecker product of graphs have been reported. Bresar andSpacapan3obtained some bounds o
9、n the edge-connectivity of Kronecker products of graphs， and upper bounds on the connectivity of the Kronecker products of graphs. Mamut and Vumar4showed that（KnKm） = （n？1）（m？1） for any nm2 and n3 ； Guji and Vumar5investigated the connectivity of the Kronecker product of a connected bipartite graph
10、G and complete graph Knwith n3 and reported that（GKn） = minn（G） ， （n？1）（G）； Later， L. Guo et al.6strengthened their result by showing that for any connected bipartite graph G and complete graph Knwith n3， if（G） =（G） ， then GKnis super-. Very recently， Y. Wang and B. Wu7proved that（GKn） = minn（G） ， （
11、n？1）（G） for any connected graph G and complete graph Knwith n3. In this paper， we show that GKn（n4） is super-if and only if n（G） （G） （n？1）. Furthermore， we show that for any connected graphs G， if（G） =（G） then GKnis super-for n3. We show claim 1 by contradiction.Assume that there exist integers k，l1
12、，.，t 4and i1，.，m， such that V （Hk）Si？=？and V （Hl）Si？=？. Take a vertex （xi，a）V （Hk）Siand （xi，b）V （Hl）Si. Since S is non-trivial， there exist two vertices， say （xj，c） in V （Hk） and （xg，d）V （Hl） such that （xi，a） （xj，c） in E（Hk） and （xg，d） （xi，b）E（Hl） （g may equal to j）. Note that Hkis not connected to
13、Hlin H？S， then we have a = d and c = b. In the following， we will show that Hland Hkare connected by at least（G） （n？1）+1 internally vertex-disjoint paths. For simplicity， we usefor（G）. Let T = u1，u2，.，u？NG（xi）. We consider the subgraph F = GT of G induced by T. Take a maximum matching M of F. Let q
14、= |M| and M = u1u2， u3u4，.，u2q？1u2q， without loss of generality. There are（n？2） Type-I paths， 2q Type-II paths and n？2 Type-III paths connecting Hland Hkas defined in the following. Type-I paths： for any p1，2，.， and any yV （Kn） a，b， Ppy：（xi，a） （up，y） （xi，b）. 1 D B West. Introduction to Graph Theory.
15、 Second Edition， Prentice Hall， Upper Saddle River， NJ， 2001. 2 P M Weichesel. The Kornecher product of graphs. Proc 5Amer Math Soc， 1962， 13： 47-52. 3 B Bresar， SSpacapan. On the Connectivity of the direct product of graphs. Australas J Combin， 2008， 41： 45-56. 4 A Mamut， E Vumar. Vertex vulnerabil
16、ity parameters of Kronecker product of complete graphs. Inform Process Lett， 2008， 106： 258-262. 5 R Guji， E Vumar. A note on the connectivity of Kronecker products of graphs. Appl Math Lett， 2009， 22： 1360-1363. 6 L Guo， C Qin， X Guo. Super connectivity of Kronecker products of graphs. Inform Process Lett， 2010，110： 659-661. 7 Y Wang， B Wu. Proof of a conjecture on connectivity of Kronecker product of graphs， Discrete Math， 2011， 311： 2563-2565.
