Суммарная величина вершинного разделения графа

Вводится новый инвариант графов, названный нами суммарной величиной вершинного разделения. Показано, что задача распознавания, состоящая в том, чтобы по графу $G$ и неотрицательному целому числу $k$ проверить, верно ли, что $\operatorname{sv}(G)\le k$, где $\operatorname{sv}(G)$ — суммарная величина вершинного разделения графа $G$, является NP-полной даже для реберных графов. Решается задача вычисления данного инварианта для графов интервалов. Рассмотрен также вопрос о суммарной величине вершинного разделения деревьев.
Работа выполнена при поддержке программой Университеты России.