Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


Для цитирования:

Абросимов М. Б., Долгов А. А. О бесконтурных точных расширениях // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 2010. Т. 10, вып. 1. С. 83-88. DOI: 10.18500/1816-9791-2010-10-1-83-88

Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
18.01.2010
Полный текст:
(downloads: 195)
Язык публикации: 
русский
Рубрика: 
УДК: 
519.17

О бесконтурных точных расширениях

Авторы: 
Абросимов Михаил Борисович, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Долгов Александр Алексеевич, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Аннотация: 

Точные расширения неориентированных графов достаточно хорошо исследованы, а о точных расширениях орграфов известно значительно меньше. В данной работе доказывается, что только бесконтурный или сильно связный граф может быть точным 1-расширением орграфа. Более того, бесконтурным точным 1-расширением может быть только транзитивный турнир.

Список источников: 
  1. Harary F., Hayes J.P. Node fault tolerance in graphs // Networks. 1996. V. 27. P. 19–23.
  2. Абросимов М.Б. Минимальные расширения дополнений графов // Теоретические задачи информатики и ее приложений. Саратов: Изд-во Сарат. ун-та, 2001. Вып. 4. С. 11–19.
  3. Абросимов М.Б., Долгов А.А. Точные расширения некоторых турниров // Вестн. Томск. гос. ун-та. Приложение. 2007. № 23. С. 211–216.
  4. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997.