Cтраница 3
Решетчатый граф L2 ( m) ( m 2) имеет своими вершинами множество 5XS, где 5 - множество мощности т; две вершины этого графа смежны тогда и только тогда, когда они имеют общую координату. Объединение k непересекающихся полных графов на m вершинах каждый ( k, m - 1) также образует сильно регулярный граф T ( k, т) с параметрами п mk, а т - 1, с т - 2, а О, причем всякий сильно регулярный граф с d Q имеет такую форму. Граф Г ( &, 2) называется лестничным графом. Дополнение графа T ( k m) называется полным k - дольным графом. Если q - степень простого и 7l ( mod4), то граф ТЪли P ( q) имеет в качестве вершин элементы поля GF ( q), и две его вершины смежны тогда и только тогда, когда их разность есть ненулевой квадрат. Это сильно регулярный граф с параметрами п q, a ( q - l) / 2, c ( q - 5) / 4, d ( q - 1) / 4, изоморфный своему дополнению. [31]
Первый из них, вместе с триангулярным графом 7 ( 23), демонстрирует, что кратности собственных значений сильно регулярного графа не определяют параметра графа, даже когда известно, что это блок-граф квазисимметричной схемы. [32]
Рассматривая все 212 смежных классов и соединяя два класса ребром, если между ними расстояние один, мы получим регулярный тонкий почти восьмиугольник на 4096 вершинах, в котором описанный выше сильно регулярный граф является графом путей длиной 2 на каждой из двудольных половин. Последний был впервые построен Геталсом и Сей-делом, которые описали его следующим образом. [33]
Решетчатый граф L2 ( m) ( m 2) имеет своими вершинами множество 5XS, где 5 - множество мощности т; две вершины этого графа смежны тогда и только тогда, когда они имеют общую координату. Объединение k непересекающихся полных графов на m вершинах каждый ( k, m - 1) также образует сильно регулярный граф T ( k, т) с параметрами п mk, а т - 1, с т - 2, а О, причем всякий сильно регулярный граф с d Q имеет такую форму. Граф Г ( &, 2) называется лестничным графом. Дополнение графа T ( k m) называется полным k - дольным графом. Если q - степень простого и 7l ( mod4), то граф ТЪли P ( q) имеет в качестве вершин элементы поля GF ( q), и две его вершины смежны тогда и только тогда, когда их разность есть ненулевой квадрат. Это сильно регулярный граф с параметрами п q, a ( q - l) / 2, c ( q - 5) / 4, d ( q - 1) / 4, изоморфный своему дополнению. [34]
Тогда получим граф, содержащий Но - Si в качестве подграфа. Собственные значения ( - 1, 1 0) - матрицы смежности для этого два-графа равны pi 35 и р2 - 5 ( с кратностями ц 1 22 и Ц2 154), а для графа Но - Si ро 35, pi 5 и р2 - 5 с кратностями 1, 21 и 28, поэтому из сформулированного выше следствия вытекает существование сильно регулярного графа на 126 вершинах. Замечая, что этот граф регулярен валентности 50, мы заключаем, что это и есть требуемый граф. [35]
Тогда получим граф, содержащий Но - Si в качестве подграфа. Собственные значения ( - 1, 1, 0) - матрицы смежности для этого два-графа равны PI 35 и р2 - 5 ( с кратностями щ 22 и ц2 154), а для графа Но - Si РО 35, pi 5 и р2 - 5 с кратностями 1, 21 и 28, поэтому из сформулированного выше следствия вытекает существование сильно регулярного графа на 126 вершинах. Замечая, что этот граф регулярен валентности 50, мы заключаем, что это и есть требуемый граф. [36]
Киев: ИК АН УССР, 1978, с. О группах автоморфизмов сильно регулярных графов, инвариантных относительно экспоненцирования симметрических групп. [37]
Киев: ИК АН УССР, 1978, с. О группах автоморфизмов сильно регулярных графов, инвариантных относительно экспоненцироваиия симметрических групп. [38]
В статью включены как теоретико-групповые, так и комбинаторные аспекты обсуждаемой теории. Мы приводим список всех известных ко времени написания статьи сильно регулярных графов, а также обширную библиографию по рассматриваемому предмету. [39]
Заметим, что уравнение ( А - pi /) ( Л - ра /) 0 инвариантно относительно переключения. Это уравнение влечет, что если граф регулярен, то он сильно регулярен. Нетрудно показать, что имеются два возможных множества параметров для сильно регулярного графа в переключательном классе регулярного 2-графа. Мы видели в главе 3, что второе множество нереализуемо. Таким образом, не всегда реализуют ся обе эти возможности, хотя и дают много интересных случаев. [40]
Может быть, этот граф не относится к настоящему разделу - например, для него 2 не является собственным значением. Прямая проверка показывает, что в результате получается 2 - ( 176 50, 14) - схема. Тогда А - / является матрицей смежности требуемого сильно регулярного графа. Для этого графа S8 является группой автоморфизмов. Вопрос единственности не решен. [41]