The total vertex separation number of a graph

For a graph $G$ we introduce a new graph invariant $\operatorname{sv}(G)$ which we name the total vertex separation number. We demonstrate that the recognition problem consisting in checking whether or not $\operatorname{sv}(G)\le k$ for a given $G$ and a non-negative integer $k$ is NP-complete even for edge graphs. We consider the problem to calculate this invariant for the interval graphs. In addition, the total vertex separation number of a tree is considered.
This research was supported by the program ‘Universities of Russia’.