{
  "id": "1109.3508",
  "version": "v2",
  "published": "2011-09-15T23:08:49.000Z",
  "updated": "2012-02-16T21:43:10.000Z",
  "title": "Decompositions of Complete Multipartite Graphs into Complete Graphs",
  "authors": [
    "Ruy Fabila-Monroy",
    "David R. Wood"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $k\\geq\\ell\\geq1$ and $n\\geq 1$ be integers. Let $G(k,n)$ be the complete $k$-partite graph with $n$ vertices in each colour class. An $\\ell$-decomposition of $G(k,n)$ is a set $X$ of copies of $K_k$ in $G(k,n)$ such that each copy of $K_\\ell$ in $G(k,n)$ is a subgraph of exactly one copy of $K_k$ in $X$. This paper asks: when does $G(k,n)$ have an $\\ell$-decomposition? The answer is well known for the $\\ell=2$ case. In particular, $G(k,n)$ has a 2-decomposition if and only if there exists $k-2$ mutually orthogonal Latin squares of order $n$. For general $\\ell$, we prove that $G(k,n)$ has an $\\ell$-decomposition if and only if there are $k-\\ell$ Latin cubes of dimension $\\ell$ and order $n$, with an additional property that we call mutually invertible. This property is stronger than being mutually orthogonal. An $\\ell$-decomposition of $G(k,n)$ is then constructed whenever no prime less than $k$ divides $n$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-02-16T21:43:10.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "complete multipartite graphs",
      "complete graphs",
      "decomposition",
      "mutually orthogonal latin squares",
      "paper asks"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1109.3508F"
    }
  }
}