| 陈来焕,孟吉翔,田应智.笛卡尔乘积图的圈点连通度[J].数学年刊A辑,2016,37(2):155~170 |
| 笛卡尔乘积图的圈点连通度 |
| Cyclic Vertex Connectivity of Cartesian Product Graphs |
| Received:October 16, 2014 Revised:September 23, 2015 |
| DOI： |
| 中文关键词: 连通度, 圈点连通度, 笛卡尔乘积, 完美匹配 |
| 英文关键词:Connectivity, Cyclic vertex connectivity, Cartesian product, Perfect matching |
| 基金项目:本文受到国家自然科学基金 (No.11171283, No.11401510) 的资助. |
|
| Hits: 1573 |
| Download times: 588 |
| 中文摘要: |
| 图$G$的圈点连通度, 记为$\kappa_{c}(G)$, 是所有圈点割中最小的数目, 其中每个圈点割$S$满足$G-S$不连通且至少它的两个分支含圈.
这篇文章中给出了两个连通图的笛卡尔乘积的圈点连通度: (1)如果$G_1\cong
K_m$且$G_2\cong K_n$, 则$\kappa_c(G_1\times
G_2)=\min\{3m+n-6,m+3n-6\}$, 其中$m+n\geq8$, $m\geq n+2$, 或$n\geq
m+2$, 且 $\kappa_c(G_1\times
G_2)=2m+2n-8$, 其中$m+n\geq8$, $m=n$, 或$n=m+1$, 或$m=n+1$; (2)如果$G_1\cong
K_m(m\geq3)$且$G_2\ncong K_n$, 则
min$\{3m+\kappa(G_2)-4,m+3\kappa(G_2)-3,2m+2\kappa(G_2)-4\}\leq
\kappa_c(G_1\times G_2)\leq m\kappa(G_2)$; (3)如果$G_1\ncong
K_m,K_{1,m-1}$且$G_2\ncong
K_n,K_{1,n-1}$, 其中$m\geq4$, $n\geq4$, 则min$\{3\kappa(G_1)+\kappa(G_2)-1,\kappa(G_1)+3\kappa(G_2)-1,2\kappa(G_1)+2\kappa(G_2)-2\}\leq\kappa_c(G_1\times
G_2)\leq \min\{m\kappa(G_2),n\kappa(G_1),2m+2n-8\}$. |
| 英文摘要: |
| The cyclic vertex connectivity of a graph $G$, denoted by
$\kappa_{c}(G)$, is the minimum cardinality of all cyclic
vertex-cuts, where each cyclic vertex-cut $S$ satisfies that $G-S$ is
disconnected, and at least two of its components contain cycles. In
this paper, the authors give the cyclic vertex connectivity of Cartesian
product of two connected graphs as follows: (1) If $G_1\cong K_m$
and $G_2\cong K_n$, then $\kappa_c(G_1\times
G_2)=\min\{3m+n-6,m+3n-6\}$ for $m+n\geq8$ and $m\geq n+2$, or
$n\geq m+2$, and $\kappa_c(G_1\times G_2)=2m+2n-8$ for $m+n\geq8$
and $m=n$, or $n=m+1$, or $m=n+1$; (2) If $G_1\cong K_m\ (m\geq3)$ and
$G_2\ncong K_n$, then
min$\{3m+\kappa(G_2)-4,m+3\kappa(G_2)-3,2m+2\kappa(G_2)-4\}\leq
\kappa_c(G_1\times G_2)\leq m\kappa(G_2)$; (3) If $G_1\ncong
K_m,K_{1,m-1}$ and $G_2\ncong K_n,K_{1,n-1}$ for $m\geq4$ and
$n\geq4$, then
min$\{3\kappa(G_1)+\kappa(G_2)-1,\kappa(G_1)+3\kappa(G_2)-1,2\kappa(G_1)+2\kappa(G_2)-2\}\leq\kappa_c(G_1\times
G_2)\leq \min\{m\kappa(G_2),n\kappa(G_1),2m+2n-8\}$. |
| View Full Text View/Add Comment Download reader |
| Close |
|
|
|
|
|
