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

Статья

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

Описывается класс графов, у которых для каждого подграфа максимальное число вершинно непересекающихся 4-путей равно минимальной мощности множества вершин таких, что каждый 4-путь подграфа содержит хотя бы одну из этих вершин. Полностью описано множество минимальных запрещенных подграфов данного класса. Кроме того, представлено альтернативное описание класса, в основе которого лежит операция подразбиения ребер, применяемая к двудольным мультиграфам, и добавление так называемых висячих подграфов, изоморфных треугольникам и звездам.