Том 20, номер 2, 2013 г., Стр. 3-14

УДК 519.17
Горяинов С. В., Шалагинов Л. В.
О графах Деза с параметрами графов, дополнительных к треугольным и решётчатым

Аннотация:
Рассматриваются точные графы Деза, полученные из графов, дополнительных к треугольным и решётчатым, графам Чанга и графу Шрикханде с помощью их автоморфизмов порядка два. Показано, что эти графы определяются параметрами и строением окрестностей в классе точных графов Деза.
Библиогр. 11.

Ключевые слова: граф Деза, инволютивный автоморфизм.

Горяинов Сергей Викторович ¹
Шалагинов Леонид Викторович ²
1. Челябинский гос. университет,
ул. Бр. Кашириных, 129, 454001 Челябинск, Россия
2. Институт математики и механики УрО РАН,
ул. С.Ковалевской, 16, 620990 Екатеринбург, Россия
е-mail: 44g@mail.ru, leonidshalaginov@rambler.ru

Статья поступила 10 мая 2012 г.
Исправленный вариант — 27 августа 2012 г.

Литература

[1] Горяинов С. В., Шалагинов Л. В. О графах Деза на 14, 15 и 16 вершинах // Сиб. электрон. мат. изв. - 2011. - Т. 8. - С. 105–115.

[2] Кабанов В. В., Шалагинов Л. В. О графах Деза с параметрами решётчатых графов // Тр. ИММ УрО РАН. - 2010. - Т. 3. - С. 117–120.

[3] Шалагинов Л. В. О графах Деза с параметрами треугольных графов // Тр. ИММ УрО РАН. - 2011. - Т. 1. - С. 294–298.

[4] Bose R. C. Strongly regular graphs, partial geometries and partially balanced designs // Pacific J. Math. - 1963. - Vol. 13. - P. 389–419.

[5] Brouwer A. E., Cohen A. M., Neumaier A. Distance regular graphs. - Berlin: Springer-Verl., 1989. - 495 p.

[6] Chang L. C. The uniqueness and nonuniqueness of the triangular association scheme // Sci. Record. - 1959. - Vol. 3. - P. 604–613.

[7] Deza M., Deza A. The ridge graph of the metric polytope and some relatives // Polytopes: abstract, convex, and computational. NATO ASI Ser. - New York: Kluwer Acad., 1994. - P. 359–372.

[8] Erickson M., Fernando S., Haemers W. H., Hardy D., Hemmeter J. Deza graphs: a generalization of strongly regular graphs // J. Comb. Des. - 1999. - Vol. 7. - P. 359–405.

[9] Higman D. G. Finite permutations group of rank 3 // Math. Z. - 1964. - Bd 86. - S. 145–156.

[10] Hoffman A. J. On the uniqueness of the triangular association scheme // Ann. Math. Stat. - 1960. - Vol. 31. - P. 492–497.

[11] Shrikhande S. S. The uniqueness of the L₂ association scheme // Ann. Math. Stat. - 1959. - Vol. 30. - P. 781–798.