{
  "id": "1106.1255",
  "version": "v1",
  "published": "2011-06-07T04:00:21.000Z",
  "updated": "2011-06-07T04:00:21.000Z",
  "title": "Connectivity of Kronecker products by K2",
  "authors": [
    "Wei Wang",
    "Zhidan Yan"
  ],
  "comment": "6 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $\\kappa(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_1u_2\\in E(G_1),v_1v_2\\in E(G_2)\\}$. In this paper, we prove that $\\kappa(G\\times K_2)=\\textup{min}\\{2\\kappa(G), \\textup{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$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-06-07T04:00:21.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C40",
      "05C40"
    ],
    "keywords": [
      "kronecker product",
      "connectivity",
      "vertex set",
      "edge set",
      "disjoint sets"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1106.1255W"
    }
  }
}