Том 12, серия 1, номер 4, 2005 г., Стр. 3-22

УДК 519.71
И. А. Вакула, В. В. Кабанов
О графах без 3-лап с некликовыми $\mu$-подграфами

Аннотация:
Исследуются связные графы, в которых любые две вершины, находящиеся на расстоянии 2 друг от друга, лежат в порождённом 4-цикле. Доказывается, что: 1) если такой граф не содержит порождённых $\mathsf K_{1,3}$ подграфов, редуцирован и содержит 4-коклику, то он является рёберным графом; 2) если такой граф является рёберным, то он является рёберным графом некоторого полного многодольного графа.

Вакула И. А. ¹
Кабанов В. В. ¹
1. Институт математики и механики УрО РАН,
ул. Ковалевской, 16, 620219 Екатеринбург, Россия
е-mail: vvk@imm.uran.ru

Статья поступила 27 сентября 2004 г.
Исправленный вариант — 12 апреля 2005 г.