{
  "id": "2307.10661",
  "version": "v1",
  "published": "2023-07-20T07:44:30.000Z",
  "updated": "2023-07-20T07:44:30.000Z",
  "title": "Mutual-visibility in distance-hereditary graphs: a linear-time algorithm",
  "authors": [
    "Serafino Cicerone",
    "Gabriele Di Stefano"
  ],
  "comment": "16 pages, 5 figures, a preliminary version will appear on the proc. of the XII Latin and American Algorithms, Graphs and Optimization Symposium, {LAGOS} 2023, Huatulco, Mexico, September 18-22, 2023. Procedia Computer Science, Elsevier",
  "categories": [
    "math.CO",
    "cs.DS"
  ],
  "abstract": "The concept of mutual-visibility in graphs has been recently introduced. If $X$ is a subset of vertices of a graph $G$, then vertices $u$ and $v$ are $X$-visible if there exists a shortest $u,v$-path $P$ such that $V(P)\\cap X \\subseteq \\{u, v\\}$. If every two vertices from $X$ are $X$-visible, then $X$ is a mutual-visibility set. The mutual-visibility number of $G$ is the cardinality of a largest mutual-visibility set of $G$. It is known that computing the mutual-visibility number of a graph is NP-complete, whereas it has been shown that there are exact formulas for special graph classes like paths, cycles, blocks, cographs, and grids. In this paper, we study the mutual-visibility in distance-hereditary graphs and show that the mutual-visibility number can be computed in linear time for this class.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-07-20T07:44:30.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "G.2.2",
      "F.2.2",
      "G.2.1"
    ],
    "keywords": [
      "distance-hereditary graphs",
      "linear-time algorithm",
      "mutual-visibility number",
      "special graph classes",
      "largest mutual-visibility set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}