{
  "id": "2310.07104",
  "version": "v1",
  "published": "2023-10-11T00:57:54.000Z",
  "updated": "2023-10-11T00:57:54.000Z",
  "title": "On the edge reconstruction of the characteristic and permanental polynomials of a simple graph",
  "authors": [
    "Jingyuan Zhang",
    "Xian'an Jin",
    "Weigen Yan",
    "Qinghai Liu"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "As a variant of the Ulam's vertex reconstruction conjecture and the Harary's edge reconstruction conjecture, Cvetkovi\\'c and Schwenk posed independently the following problem: Can the characteristic polynomial of a simple graph $G$ with vertex set $V$ be reconstructed from the characteristic polynomials of all subgraphs in $\\{G-v|v\\in V\\}$ for $|V|\\geq 3$? This problem is still open. A natural problem is: Can the characteristic polynomial of a simple graph $G$ with edge set $E$ be reconstructed from the characteristic polynomials of all subgraphs in $\\{G-e|e\\in E\\}$? In this paper, we prove that if $|V|\\neq |E|$, then the characteristic polynomial of $G$ can be reconstructed from the characteristic polynomials of all subgraphs in $\\{G-uv, G-u-v|uv\\in E\\}$, and the similar result holds for the permanental polynomial of $G$. We also prove that the Laplacian (resp. signless Laplacian) characteristic polynomial of $G$ can be reconstructed from the Laplacian (resp. signless Laplacian) characteristic polynomials of all subgraphs in $\\{G-e|e\\in E\\}$ (resp. if $|V|\\neq |E|$).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-10-11T00:57:54.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "characteristic polynomial",
      "simple graph",
      "permanental polynomial",
      "ulams vertex reconstruction conjecture",
      "hararys edge reconstruction conjecture"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}