Том 16, номер 4, 2009 г., Стр. 87-96

УДК 519.1
П. В. Скумс, Р. И. Тышкевич
Гипотеза реконструируемости для графов с ограничениями на 4-вершинные простые цепи

Аннотация:
Исследуется широко известная гипотеза Келли–Улама о реконструируемости. Показано, что гипотеза верна для $P_4$-несвязных и $P_4$-хороших ($P_4$-tidy) графов. В частности, тем самым обобщаются известные результаты о реконструируемости несвязных графов, дополнений несвязных графов, 1-разложимых графов и $P_4$-сжимаемых графов.
Библиогр. 19.

Ключевые слова: гипотеза реконструируемости, $P_4$-несвязные графы, $P_4$-хорошие графы, $P_4$-сжимаемые графы, 1-разложимые графы.

Скумс Павел Валентинович ¹
Тышкевич Регина Иосифовна ¹
1. Белорусский государственный университет,
пр. Независимости, 4, 220030 Минск, Беларусь
е-mail: skumsp@gmail.com, tyshkevich@bsu.by

Статья поступила 29 января 2009 г.
Исправленный вариант — 22 мая 2009 г.