• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

Кениговы графы относительно 5-пути и его остовных надграфов

Описывается наследственный класс графов, обладающих свойством равенства максимального числа вершинно не пересекающихся 5-путей (путей из 5 вершин) и минимальной мощности множества вершин, имеющего непустое пересечение с множеством вершин каждого 5-пути. Дано описание данного класса в терминах "запрещённых подграфов", а также альтернативное описание класса, в основе которого лежит построение графов из псевдографов с использованием различных операций.