Задача нахождения хеллиевой размерности графа

Abstract

The paper deals with helly dimension of graph – such minimal number r so that every vertex in the graph belongs to at most r maximal cliques. It is proven that the problem of calculation helly dimension is #P in arbitrary case. It is proven that this task is polynomially solvable in the class of domishold graphs and linear algorithm is presented that calculates helly dimension of domishold graph by its degree sequence. = Исследуется хеллиева размерность графа – такого минимального числа r, что каждая вершина графа принадлежит не более r максимальным кликам. Доказана #P-полнота задачи нахождения хеллиевой размерности в произвольном случае, а также, что задача полиномиально разрешима в классе доминантно-пороговых графов, и приведен линейный алгоритм, вычисляющий хеллиеву размерность по степенной последовательности графа из указанного класса. Даны условия, при которых хеллиева размерность полиномиально зависит от числа вершин в доминантно-пороговом графе.