Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/dfc/2010/Program1/Obraztsova_summary.pdf Дата изменения: Thu Oct 14 10:02:00 2010 Дата индексирования: Sun Feb 13 23:22:43 2011 Кодировка: Windows-1251 Поисковые слова: universe

О локальной структуре k -связных графов. (Краткий план исследований С.Образцовой.)

Количество вершин графа G мы будем обозначать |G|. Будем говорить, что связный граф G называется k-связным, если |G| > k и при удалении любого (k - 1)-элементного подмножества множества его вершин он сохраняет связность. Исследование посвящено k-связным графам, которые перестают быть k-связными при удалении или стягивании любого из ребер (то есть являются минимальными и минимальными по стягиванию ). Изучение минимальных и минимальных по стягиванию k-связных графов началось в 60-х годах прошлого века с работ В.Татта и Р.Халина. Именно Р.Халин сформулировал задачу о нахождении такой константы ck , что количество вершин степени k в минимальном и минимальном по стягиванию k-связном графе G равно по крайней мере ck |G|. Он же получил и первые нижние оценки для ck . В дальнейшем, в основном, велись исследования графов, обладающих только одним из двух свойств - минимальностью или минимальностью по стягиванию. В первом направлении получены нижние оценки на долю вершин степени k среди всех вершин графа для любого k, во втором верхние и нижние оценки для k 7. Оценки, полученные автором, лучше имевшихся оценок как первого, так и второго типа. Проведенные исследования Автором доказано несколько лемм, описывающих структуру k-связных графов, двух основных типов, описывающих условия при которых вершина, имеющая степень k, смежна хотя бы с одной вершиной степени k, и описывающих свойства окрестностей особых вершин. С помощью структурных лемм были доказаны следующие нижние оценки на количество вершин степени k в k-связных графах: 4 для 5-связных 7 1 графов и 2 для 6,7 и 8-связных. Проект будущих исследований В дальнейшем предполагается изучить структуру минимальных и минимальных по стягиванию 9 и 10-связных графов и доказать для этих графов нижнюю оценку аналогичную случаям 6, 7, 8. С этой целью автор намеревается доказать серию структурных лемм, в частности, описывающих окрестности особых вершин специального вида (в минимальных и минимальных по стягиванию графах меньшей связности таких особых вершин не существует). Кроме того, планируется доказать и асимптотические верхние оценки для ck . 5 ћ Для k = 5 предполагаемая верхняя оценка 22 , ћ для k > 5 предполагаемая верхняя оценка 5k2 . +3 1