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

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

Cyclic Vertex Connectivity of Cartesian Product Graphs

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\}$.