This article is cited in 4 papers

The total vertex separation number of a graph

P. A. Golovach


Abstract: 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’.

UDC: 519.717

Received: 25.05.1994

DOI: 10.4213/dm506

 English version: Discrete Mathematics and Applications, 1997, 7:6, 631–636

Bibliographic databases:

• 
•