Hangable Graphs

Mateusz Miotk; Jerzy Topp

paper

Hangable Graphs

arXiv:1512.07767

Abstract

Let $G = (V_{G}, E_{G})$ be a connected graph. The distance $d_{G} (u, v)$ between vertices $u$ and $v$ in $G$ is the length of a shortest $u - v$ path in $G$ . The eccentricity of a vertex $v$ in $G$ is the integer $e_{G} (v) = max {d_{G} (v, u) : u \in V_{G}}$ . The diameter of $G$ is the integer $d (G) = max {e_{G} (v) : v \in V_{G}}$ . The periphery of a~vertex $v$ of $G$ is the set $P_{G} (v) = {u \in V_{G} : d_{G} (v, u) = e_{G} (v)}$ , while the periphery of $G$ is the set $P (G) = {v \in V_{G} : e_{G} (v) = d (G)}$ . We say that graph $G$ is hangable if $P_G(v)\subequal P(G)$ for every vertex $v$ of $G$ . In this paper we prove that every block graph is hangable and discuss the hangability of products of graphs.