笛卡尔乘积图的圈点连通度

• 作者: 孟吉翔 田应智 陈来焕
• 来源期刊: 数学年刊A辑
• 学科: 数学
• 关键词: 连通度 圈点连通度 笛卡尔乘积 完美匹配
• 年，卷（期）: 2016,（2）
• 页码范围: 155-170
• 页数: 16页
• 分类号: O157.5
• 语种: 中文
• DOI: 10.16205/j.cnki.cama.2016.0015

摘要

图G的圈点连通度,记为κc(G),是所有圈点割中最小的数目,其中每个圈点割S满足G-S不连通且至少它的两个分支含圈.这篇文章中给出了两个连通图的笛卡尔乘积的圈点连通度:(1)如果G1(≌)Km且G2(≌)Kn,则κc(G1×G2)=min{3m+n-6,m+3n-6},其中m+n≥8,m≥n+2,或n≥m+2,且κc(G1×G2)=2m+2n-8,其中m+n≥8,m=n,或n=m+1,或m=n+1;(2)如果G1(≌)Km(m≥3)且G2(≠)Kn,则min{3m+κ(G2)-4,m+3κ(G2)-3,2m+2κ(G2)-4}≤κc(G1×G2)≤moκ(G2);(3)如果G1(≠)Km,K1,m-1且G2(≠)Kn,K1,n-1,其中m≥4,n≥4,则min{3κ(G1)+κ(G2)-1,κ(G1)+3κ(G2)-1,2κ(G1)+ 2κ(G2)-2}≤κc(G1×G2)≤min{mκ(G2),nκ(G1),2m+ 2n-8}.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孟吉翔		47	90	6.0	7.0
2	陈来焕		5	5	2.0	2.0
3	田应智		14	11	2.0	2.0