Однозначно раскрашиваемые графы с минимумом рёбер

Аннотация

В работе построен граф с количеством рёбер, минимально допустимым для однозначно K-раскрашиваемого графа. Показано, как при помощи операций двух типов указанный граф можно преобразовать в множество всех графов этого класса (для произвольно заданного числа вершин). Доказано, что все такие графы (K-1)-связны. Найдено выражение для числа рёбер в таких графах, а также даны уравнения, полезные для практических целей, в частности, для различных задач оптимизации.