Super-connectivity of Kronecker products of split graphs, powers of cycles, powers of paths and complete graphs
Super-connectivity of Kronecker products of split graphs, powers of cycles, powers of paths and complete graphs
复制标题
分裂图、循环幂、路径幂和完全图的克罗内克乘积的超连通性
DOI：
10.1016/j.aml.2012.04.006
复制
发表时间：
2013
影响因子：
3.7
通讯作者：
Guo, Xiaofeng
中科院分区：
文献类型：
--
作者：
Guo, Litao;Yang, Weihua;Guo, Xiaofeng
两个连通图G1，G2的Kronecker积，记为G1×G2，是顶点集V（G1×G2）=V（G1）×V（G2），边集E（G1×G2）={（u1，v1）（u2，v2）：u1 u2 ∈E（G1），v1 v2 ∈E（G2）}的图. G的k次幂Gkof是顶点集V（G）使得两个不同的顶点在Gkif且仅当它们在G中的距离至多为k时在Gkf中相邻的图。一个连通图G称为超κ，如果G的每个极小点割都是G中某个点的邻域集.在本文中，我们考虑了几种图和完全图的克罗内克积的超连通性。我们证明了当m≥3且G满足下列条件之一时，D=G×Kmis super-κ：（1）G是不完全分裂图，且|C|（2）G是路Pnk的幂图，使得n≥2k;（3）G是圈Cnr的幂图，使得n≥m且n≥ 2 r +1.
The Kronecker product of two connected graphs G1,G2, denoted by G1×G2, is the graph with vertex set V(G1×G2)=V(G1)×V(G2) and edge set E(G1×G2)={(u1,v1)(u2,v2):u1u2∈E(G1),v1v2∈E(G2)}. The kth power Gkof G is the graph with vertex set V(G) such that two distinct vertices are adjacent in Gkif and only if their distance apart in G is at most k. A connected graph G is called super-κ if every minimal vertex cut of G is the set of neighbors of some vertex in G. In this note, we consider the super-connectivity of the Kronecker products of several kinds of graphs and complete graphs. We show that D=G×Kmis super-κ for m≥3 and G satisfying one of the following conditions: (1) G is a non-complete split graph with |C|≥5; (2) G is a power graph of a path Pnksuch that n≥2k; (3) G is a power graph of a cycle Cnrsuch that n≥m and n≥2r+1.
登录
查看更多内容
DOI：
10.1016/j.ipl.2007.12.002
发表时间：
2008-06
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
Aygul Mamut;Elkin Vumar
通讯作者：
Aygul Mamut;Elkin Vumar
影响因子：
1.7
作者：
H. Whitney
通讯作者：
H. Whitney
DOI：
10.1201/9780429425134
发表时间：
2018-11
期刊：
--
影响因子：
--
作者：
J. Gross;Jay Yellen;Mark Anderson
通讯作者：
J. Gross;Jay Yellen;Mark Anderson
DOI：
10.1137/s0895480103438358
发表时间：
2005-04
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
B. Brešar;W. Imrich;S. Klavžar;B. Zmazek
通讯作者：
B. Brešar;W. Imrich;S. Klavžar;B. Zmazek
影响因子：
--
作者：
S. Ghozati
通讯作者：
S. Ghozati