{
  "id": "2407.02102",
  "version": "v1",
  "published": "2024-07-02T09:40:20.000Z",
  "updated": "2024-07-02T09:40:20.000Z",
  "title": "Separating the edges of a graph by cycles and by subdivisions of $K_4$",
  "authors": [
    "Fábio Botler",
    "Tássio Naia"
  ],
  "comment": "10 pages, 7 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "A separating system of a graph $G$ is a family $\\mathcal{S}$ of subgraphs of $G$ for which the following holds: for all distinct edges $e$ and $f$ of $G$, there exists an element in $\\mathcal{S}$ that contains $e$ but not $f$. Recently, it has been shown that every graph of order $n$ admits a separating system consisting of $19n$ paths [Bonamy, Botler, Dross, Naia, Skokan, Separating the Edges of a Graph by a Linear Number of Paths, Adv. Comb., October 2023], improving the previous almost linear bound of $\\mathrm{O}(n\\log^\\star n)$ [S. Letzter, Separating paths systems of almost linear size, Trans. Amer. Math. Soc., to appear], and settling conjectures posed by Balogh, Csaba, Martin, and Pluh\\'ar and by Falgas-Ravry, Kittipassorn, Kor\\'andi, Letzter, and Narayanan. We investigate a natural generalization of these results to subdivisions of cliques, showing that every graph admits both a separating system consisting of $41n$ edges and cycles, and a separating system consisting of $82 n$ edges and subdivisions of $K_4$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-07-02T09:40:20.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "subdivisions",
      "separating system consisting",
      "linear bound",
      "graph admits",
      "natural generalization"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}