{
  "id": "2403.15645",
  "version": "v1",
  "published": "2024-03-22T22:56:40.000Z",
  "updated": "2024-03-22T22:56:40.000Z",
  "title": "Mutual-visibility problems in Kneser and Johnson graphs",
  "authors": [
    "Gülnaz Boruzanli Ekinci",
    "Csilla Bujtás"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be a connected graph and $\\cal X \\subseteq V(G)$. By definition, two vertices $u$ and $v$ are $\\cal X$-visible in $G$ if there exists a shortest $u,v$-path with all internal vertices being outside of the set $\\cal X$. The largest size of $\\cal X$ such that any two vertices of $G$ (resp. any two vertices from $\\cal X$) are $\\cal X$-visible is the total mutual-visibility number (resp. the mutual-visibility number) of $G$. In this paper, we determine the total mutual-visibility number of Kneser graphs, bipartite Kneser graphs, and Johnson graphs. The formulas proved for Kneser, and bipartite Kneser graphs are related to the size of transversal-critical uniform hypergraphs, while the total mutual-visibility number of Johnson graphs is equal to a hypergraph Tur\\'an number. Exact values or estimations for the mutual-visibility number over these graph classes are also established.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-03-22T22:56:40.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C12",
      "05C38",
      "05C65",
      "05C76"
    ],
    "keywords": [
      "johnson graphs",
      "total mutual-visibility number",
      "mutual-visibility problems",
      "bipartite kneser graphs",
      "hypergraph turan number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}