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.