On the uniqueness of exact vertex extensions.pdf Граф с симметричным и антирефлексивным отношением смежности называетсянеориентированным графом (далее неографом). Граф с антисимметричным отноше-нием смежности называется направленным графом или диграфом.Граф G* называется точным вершинным k-расширением графа G, если любойграф, получающийся удалением произвольных k вершин графа G*, изоморфен гра-фу G.Точное вершинное k-расширение является частным случаем минимального вер-шинного k-расширения. Известно, что в общем случае граф может иметь много неизо-морфных минимальных вершинных k-расширений. В работе [1] доказывается, что еслинеограф с числом вершин n > 1 имеет точное вершинное k-расширение, то оно яв-ляется и его минимальным вершинным k-расширением, более того, неограф с числомвершин n > 1 может иметь только одно точное вершинное k-расширение. Если бы ока-залось, что некоторый граф G имеет два или более точных вершинных 1-расширения,то эти графы были бы нереконструируемыми, так как они имели бы одинаковый набормаксимальных подграфов, который состоит из единственного графа G. Для ориенти-рованных графов ситуация оказывается более сложной, так как, с одной стороны, нетполного описания общего вида точных вершинных k-расширений, а с другой стороны,известно, что существуют нереконструируемые орграфы.Пара 3-вершинных турниров (циклическая тройка и транзитивная тройка) явля-ются неизоморфными точными вершинными 1-расширениями одного и того же 2-вер-шинного турнира. Для точных вершинных 1-расширений с числом вершин больше 3,являющихся транзитивными турнирами или вершинно-симметрическими орграфами,единственность доказана [2, 3]. В этих же работах описываются результаты вычис-лительного эксперимента, который показал, что все точные вершинные 1-расширенияорграфов с числом вершин 2 < n ^ 12 являются единственными.Известно, что орграфы в общем случае являются нереконструируемыми. Так, се-мействами нереконструируемых диграфов являются шесть семейств Стокмейера [4].Удалось установить следующий результат.Теорема 1. Диграфы из семейств Стокмейера не являются точными вершинны-ми 1-расширениями никаких орграфов.Полученный результат означает, что если существует орграф с числом вершинбольше 2, который имеет два или более неизоморфных точных вершинных 1-расши-рения, то число вершин этого орграфа не менее 13, а его точные вершинные 1-рас-ширения являются нереконструирумыми и не входят ни в одноизвестное семействонереконструируемых орграфов.

Скачать электронную версию публикации