{
  "id": "2505.04929",
  "version": "v1",
  "published": "2025-05-08T04:06:05.000Z",
  "updated": "2025-05-08T04:06:05.000Z",
  "title": "Nordhaus-Gaddum-type theorems for maximum average degree",
  "authors": [
    "Yair Caro",
    "Zsolt Tuza"
  ],
  "comment": "46 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A $k$-decomposition $(G_1,\\dots,G_k)$ of a graph $G$ is a partition of its edge set into $k$ spanning subgraphs $G_1,\\dots,G_k$. The classical theorem of Nordhaus and Gaddum bounds $\\chi(G_1) + \\chi(G_2)$ and $\\chi(G_1) \\chi(G_2)$ over all 2-decompositions of $K_n$. For a graph parameter $p$, let $p(k,G) = \\max \\{ \\sum_{i=1}^k p(Gi) \\}$, taken over all $k$-decompositions of graph $G$. In this paper we consider $M(k,K_n) = M(k,n) = \\max \\{ \\sum_{i=1}^k \\mathrm{Mad}(G_i) \\}$, taken over all $k$-decompositions of the complete graph $K_n$, where $\\mathrm{Mad}(G)$ denotes the maximum average degree of $G$, $\\mathrm{Mad}(G) = \\max \\{ 2e(H)/|H| : H \\subseteq G \\} = \\max \\{d(H) : H \\subseteq G \\}$. Among the many results obtained in this paper we mention the following selected ones. (1) $M(k, n) < \\sqrt{k} n$, and $\\lim_{k\\to\\infty} ( \\liminf_{n\\to\\infty} \\frac{M(k,n)}{\\sqrt{k}\\,n} ) = 1$. (2) Exact determination of $M(2,n)$. (3) Exact determination of $M(k,n)$ when $k = \\binom{n}{2} - t$, $0 \\leq t\\leq (n-1)^2/3$. Applications of these bounds to other parameters considered before in the literature are given.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2025-05-08T04:06:05.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05B05",
      "05C07",
      "05C35"
    ],
    "keywords": [
      "maximum average degree",
      "nordhaus-gaddum-type theorems",
      "exact determination",
      "decomposition",
      "graph parameter"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 46,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}