Kronecker乘积图的超连通性(英文)论文
作者:网友分享
网站原创
点赞:3774
浏览:9085
最后更新时间:2024-03-03
网站原创
点赞:3774
浏览:9085
最后更新时间:2024-03-03
AbstractLet G1 and G2 be two connected graphs. The Kronecker product G1×G2 is the graph with vertex set V （G1×G2） = V （G1）×V （G2） and the edge set E（G1×G2） = {（u1，v1）（u2，v2） ： u1u2∈E（G1），v1v2∈E（G2）}. In this note， we show that G×Kn （n≥4） is super-κif and only ifκ（G）n >δ（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， ifκ（G） =δ（G） then G×Kn is super-κfor n≥3. This result strengthens the known results of Guo et al..
Key wordsKronecker product； Connectivity； Super connectivity
CLC numberO 15Document codeA
1Introduction
There he 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 network.
All graphs considered in this paper arefinite， simple and connected. For notation and terminology not defined here， we refer to West[1]. The connectivity of a simple graph G is the number， denoted byκ（G）， equal to the fewest number of vertices whose removal from 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 trivial， 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 G1×G2of graphs G1and G2is the graph with the vertex set V （G1）×V （G2）， in which two vertex（u1，v1） and （u2，v2） are adjacent if and only if u1u2∈E（G1） and v1v2∈E（G2）. Hence， it is clear that the degree of a vertex（u，v） in G1×G2is equal to dG1（u）dG2（v）.
Weichsel[2]proved that if G1and G2are two connected graphs， then G1×G2is connected if and only if G1and 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 results on the connectivity of the Kronecker product of graphs he been reported. Breˇsar andˇSpacapan[3]obtained 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 Vumar[4]showed thatκ（Kn×Km） = （n？1）×（m？1） for any n≥m≥2 and n≥3； Guji and Vumar[5]investigated the connectivity of the Kronecker product of a connected bipartite graph G and complete graph Knwith n≥3 and reported thatκ（G×Kn） = min{nκ（G），（n？1）δ（G）}； Later， L. Guo et al.[6]strengthened their result by showing that for any connected bipartite graph G and complete graph Knwith n≥3， ifκ（G） =δ（G）， then G×Knis super-κ. Very recently， Y. Wang and B. Wu[7]proved thatκ（G×Kn） = min{nκ（G），（n？1）δ（G）} for any connected graph G and complete graph Knwith n≥3. In this paper， we show that G×Kn（n≥4） is super-κif and only if nκ（G） >δ（G）（n？1）. Furthermore， we show that for any connected graphs G， ifκ（G） =δ（G） then G×Knis super-κfor n≥3.
Key wordsKronecker product； Connectivity； Super connectivity
CLC numberO 15Document codeA
1Introduction
There he 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 network.
All graphs considered in this paper arefinite， simple and connected. For notation and terminology not defined here， we refer to West[1]. The connectivity of a simple graph G is the number， denoted byκ（G）， equal to the fewest number of vertices whose removal from 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 trivial， 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 G1×G2of graphs G1and G2is the graph with the vertex set V （G1）×V （G2）， in which two vertex（u1，v1） and （u2，v2） are adjacent if and only if u1u2∈E（G1） and v1v2∈E（G2）. Hence， it is clear that the degree of a vertex（u，v） in G1×G2is equal to dG1（u）dG2（v）.
Weichsel[2]proved that if G1and G2are two connected graphs， then G1×G2is connected if and only if G1and 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 results on the connectivity of the Kronecker product of graphs he been reported. Breˇsar andˇSpacapan[3]obtained 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 Vumar[4]showed thatκ（Kn×Km） = （n？1）×（m？1） for any n≥m≥2 and n≥3； Guji and Vumar[5]investigated the connectivity of the Kronecker product of a connected bipartite graph G and complete graph Knwith n≥3 and reported thatκ（G×Kn） = min{nκ（G），（n？1）δ（G）}； Later， L. Guo et al.[6]strengthened their result by showing that for any connected bipartite graph G and complete graph Knwith n≥3， ifκ（G） =δ（G）， then G×Knis super-κ. Very recently， Y. Wang and B. Wu[7]proved thatκ（G×Kn） = min{nκ（G），（n？1）δ（G）} for any connected graph G and complete graph Knwith n≥3. In this paper， we show that G×Kn（n≥4） is super-κif and only if nκ（G） >δ（G）（n？1）. Furthermore， we show that for any connected graphs G， ifκ（G） =δ（G） then G×Knis super-κfor n≥3.