Connectivity of Kronecker products by K2

Wei Wang; Zhidan Yan

paper

Connectivity of Kronecker products by K2

arXiv:1106.1255

Abstract

Let $κ (G)$ be the connectivity of $G$ . The Kronecker product $G_{1} \times G_{2}$ of graphs $G_{1}$ and $G_{2}$ has vertex set $V (G_{1} \times G_{2}) = V (G_{1}) \times V (G_{2})$ and edge set $E (G_{1} \times G_{2}) = {(u_{1}, v_{1}) (u_{2}, v_{2}) : u_{1} u_{2} \in E (G_{1}), v_{1} v_{2} \in E (G_{2})}$ . In this paper, we prove that $κ (G \times K_{2}) = min {2 κ (G), min {∣ X ∣ + 2∣ Y ∣}}$ , where the second minimum is taken over all disjoint sets $X, Y \subseteq V (G)$ satisfying (1) $G - (X \cup Y)$ has a bipartite component $C$ , and (2) $G [V (C) \cup {x}]$ is also bipartite for each $x \in X$ .

6 pages