The open hub number of a graph

Abstract

Let $G=(V, E)$ be a connected graph. A subset $H$ of $V$ is called a hub set of $G$ if for any two distinct vertices $u, v \in V-H$, there exists a $u-v$ path $P$ in $G$ such that all the internal vertices of $P$ are in $\mathrm{H}$. A hub set $H$ of $V$ is called an open hub set if the induced sub graph $\langle H\rangle$ has no isolated vertices. The minimum cardinality of an open hub set of $G$ is called the open hub number of $G$ and is denoted by $h_O(G)$. In this paper, we present several basic results on the open hub number.