Для цитирования:
Абросимов М. Б., Долгов А. А. О бесконтурных точных расширениях // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 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: 161)
Язык публикации:
русский
Рубрика:
УДК:
519.17
О бесконтурных точных расширениях
Авторы:
Абросимов Михаил Борисович, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Долгов Александр Алексеевич, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Аннотация:
Точные расширения неориентированных графов достаточно хорошо исследованы, а о точных расширениях орграфов известно значительно меньше. В данной работе доказывается, что только бесконтурный или сильно связный граф может быть точным 1-расширением орграфа. Более того, бесконтурным точным 1-расширением может быть только транзитивный турнир.
Ключевые слова:
Список источников:
- Harary F., Hayes J.P. Node fault tolerance in graphs // Networks. 1996. V. 27. P. 19–23.
- Абросимов М.Б. Минимальные расширения дополнений графов // Теоретические задачи информатики и ее приложений. Саратов: Изд-во Сарат. ун-та, 2001. Вып. 4. С. 11–19.
- Абросимов М.Б., Долгов А.А. Точные расширения некоторых турниров // Вестн. Томск. гос. ун-та. Приложение. 2007. № 23. С. 211–216.
- Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997.
- 841 просмотр