{
  "id": "2304.06453",
  "version": "v1",
  "published": "2023-04-13T12:46:36.000Z",
  "updated": "2023-04-13T12:46:36.000Z",
  "title": "On a generalization of median graphs: $k$-median graphs",
  "authors": [
    "Marc Hellmuth",
    "Sandhya Thekkumpadan Puthiyaveedu"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Median graphs are connected graphs in which for all three vertices there is a unique vertex that belongs to shortest paths between each pair of these three vertices. To be more formal, a graph $G$ is a median graph if, for all $\\mu, u,v\\in V(G)$, it holds that $|I(\\mu,u)\\cap I(\\mu,v)\\cap I(u,v)|=1$ where $I(x,y)$ denotes the set of all vertices that lie on shortest paths connecting $x$ and $y$. In this paper we are interested in a natural generalization of median graphs, called $k$-median graphs. A graph $G$ is a $k$-median graph, if there are $k$ vertices $\\mu_1,\\dots,\\mu_k\\in V(G)$ such that, for all $u,v\\in V(G)$, it holds that $|I(\\mu_i,u)\\cap I(\\mu_i,v)\\cap I(u,v)|=1$, $1\\leq i\\leq k$. By definition, every median graph with $n$ vertices is an $n$-median graph. We provide several characterizations of $k$-median graphs that, in turn, are used to provide many novel characterizations of median graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-04-13T12:46:36.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C75",
      "G.2.2"
    ],
    "keywords": [
      "median graph",
      "unique vertex",
      "novel characterizations",
      "natural generalization",
      "connected graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}