{
  "id": "2308.06670",
  "version": "v1",
  "published": "2023-08-13T03:06:48.000Z",
  "updated": "2023-08-13T03:06:48.000Z",
  "title": "Graphs with degree sequence $\\{m^{m-1},n^{n-1}\\}$ and $\\{m^n,n^m\\}$",
  "authors": [
    "Boris Brimkov",
    "Valentin Brimkov"
  ],
  "comment": "Feedback is welcome",
  "categories": [
    "math.CO"
  ],
  "abstract": "In this paper we study the class of graphs $G_{m,n}$ that have the same degree sequence as two disjoint cliques $K_m$ and $K_n$, as well as the class $\\overline G_{m,n}$ of the complements of such graphs. We establish various properties of $G_{m,n}$ and $\\overline G_{m,n}$ related to recognition, connectivity, diameter, bipartiteness, Hamiltonicity, and pancyclicity. We also show that several classical optimization problems on these graphs are NP-hard.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-08-13T03:06:48.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C07"
    ],
    "keywords": [
      "degree sequence",
      "disjoint cliques",
      "classical optimization problems",
      "complements",
      "properties"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}