{
  "id": "2210.00338",
  "version": "v1",
  "published": "2022-10-01T18:29:27.000Z",
  "updated": "2022-10-01T18:29:27.000Z",
  "title": "Reconstruction and Edge Reconstruction of Triangle-free Graphs",
  "authors": [
    "Alexander Clifton",
    "Xiaonan Liu",
    "and Reem Mahmoud",
    "Abhinav Shantanam"
  ],
  "comment": "11 pages, 3 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "The Reconstruction Conjecture due to Kelly and Ulam states that every graph with at least 3 vertices is uniquely determined by its multiset of subgraphs $\\{G-v: v\\in V(G)\\}$. Let $diam(G)$ and $\\kappa(G)$ denote the diameter and the connectivity of a graph $G$, respectively, and let $\\mathcal{G}_2:=\\{G: \\textrm{diam}(G)=2\\}$ and $\\mathcal{G}_3:=\\{G:\\textrm{diam}(G)=\\textrm{diam}(\\overline{G})=3\\}$. It is known that the Reconstruction Conjecture is true if and only if it is true for every 2-connected graph in $\\mathcal{G}_2\\cup \\mathcal{G}_3$. Balakumar and Monikandan showed that the Reconstruction Conjecture holds for every triangle-free graph $G$ in $\\mathcal{G}_2\\cup \\mathcal{G}_3$ with $\\kappa(G)=2$. Moreover, they asked whether the result still holds if $\\kappa(G)\\ge 3$. (If yes, the class of graphs critical for solving the Reconstruction Conjecture is restricted to 2-connected graphs in $\\mathcal{G}_2\\cup\\mathcal{G}_3$ which contain triangles.) In this paper, we give a partial solution to their question by showing that the Reconstruction Conjecture holds for every triangle-free graph $G$ in $\\mathcal{G}_3$ and every triangle-free graph $G$ in $\\mathcal{G}_2$ with $\\kappa(G)=3$. We also prove similar results about the Edge Reconstruction Conjecture.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-10-01T18:29:27.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C60"
    ],
    "keywords": [
      "triangle-free graph",
      "reconstruction conjecture holds",
      "edge reconstruction conjecture",
      "ulam states",
      "contain triangles"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}