Число автоморфизмов графа для графа изоморфизма

Позволять $G$ а также $H$ быть двумя $r$ регулярные связные графы размера $n$ , Позволять $A$ быть набором перестановок $P$ такой, что $PGP^{-1}=H$ , Если $G=H$ тогда $A$ это множество автоморфизмов $G$ ,

Каков самый известный верхний предел размера $A$ ?
Есть ли какие-либо результаты для конкретных классов графов (не содержащих полных / циклических графов)?

Примечание. Построение группы автоморфизмов, по крайней мере, так же сложно (с точки зрения ее вычислительной сложности), как и решение проблемы изоморфизма графов. На самом деле, простой подсчет автоморфизмов эквивалентен изоморфизму графа за полиномиальное время, см. Р. Матон, «Замечание о проблеме подсчета изоморфизмов графа».

reference-request graph-theory co.combinatorics graph-isomorphism gr.group-theory Джим
источник

Вормальд показал, что если $G$ это связано $3$ -регулярный граф с 2n вершинами, то число автоморфизмов $G$ водоразделы $3n\cdot 2^n$ , В частности, это дает нетривиальную экспоненциальную верхнюю оценку для $3$ регулярный случай. Может быть, есть результаты в этой строке для общего $k$ регулярные графы.

Для нижней границы рассмотрим формулу $F$ с $n$ входы, чьи ворота являются дополнением $\mod k$ ворота фан-ин 2. Затем, используя выход Торана, можно построить $k$ регулярный граф $G(F)$ с $O(k^2\cdot n)$ вершины, группа автоморфизмов которых кодирует все возможные оценки $F$ , Это означает, что число автоморфизмов $G(F)$ по крайней мере $k^n$ , Это показывает, что существует экспоненциальная нижняя оценка числа автоморфизмов $k$ регулярные графы в зависимости от числа вершин.

Матеус де Оливейра Оливейра
источник

Пожалуйста, рассмотрите следующий график, 1.

r_{1}

$r_1$ регулярный график и

r_{2}

$r_2$ регулярный граф (ни один из них не является полным или циклическим графом) соединяются друг с другом через число ребер E, скажем, этот объединенный граф является нерегулярным графом

G

$G$ 2. каждая вершина

r_{1}

$r_1$ регулярный граф имеет ребра с

r_{2}

$r_2$ регулярный граф. Нет двух вершин

r_{1}

$r_1$ регулярный граф, имеющий одинаковое количество ребер с

r_{2}

$r_2$ регулярный граф. Может ли автоморфизм группы G быть экспоненциальным?

Джим

да. Граф G2 может иметь экспоненциальное число автоморфизмов. Пусть H1 - любой регулярный граф r1 с n вершинами, пронумерованными 1 ... n. Пусть H2 - граф, полученный следующим процессом (разделенным на 3 комментария). Пусть D - граф алмазов, т. Е. 4-цикл вместе с ребром, соединяющим две ранее несмежные вершины. Скажем, что эти две вершины являются внутренними вершинами D. Другие две вершины являются внешними вершинами D. Ясно, что существует автоморфизм, который меняет обе внутренние вершины и оставляет внешние вершины нетронутыми.

Матеус де Оливейра Оливейра

Теперь рассмотрим несвязное объединение двух циклов C1 и C2 с n (n + 1) / 2 вершинами, пронумерованными от 1 до n (n + 1) / 2. Также рассмотрим n (n + 1) / 2 копии графа diamod. Теперь для каждого i подключите одну из внешних вершин D_i к i-й вершине C1, а другую внешнюю вершину к i-й вершине C2. Тогда граф H2, полученный этим процессом, является 3-регулярным и имеет экспоненциальное число автоморфизмов, поскольку внутренние вершины каждого D_i можно менять местами отдельно.

Матеус де Оливейра Оливейра

Теперь для каждой вершины v_j из H1 мы добавляем 2j ребер из v_j во внутренние вершины алмазов таким образом, что обе внутренние вершины алмаза D_i соединяются с одной и той же вершиной в H1. Это гарантирует, что внутренние вершины алмаза еще можно поменять местами, и поэтому общее число автоморфизмов в графе G2 экспоненциально.

Матеус де Оливейра Оливейра

Нетрудно показать, что связный граф порядка

n

$n$ и максимальной валентности

k

$k$ имеет группу автоморфизмов порядка не более

n k (k - 1)^{n - 2}

$nk(k-1)^{n-2}$ , Найдите порядок вершин таким образом, чтобы, начиная со второй, каждая вершина была смежна хотя бы с одной из предшествующих вершин. Позволять

G_{i}

$G_i$ быть подгруппой, фиксирующей первый

i

$i$ Вершины. Это нисходящая цепочка подгрупп, с

| G : G_{1} | \leq n

$|G:G_1|\leq n$ а также

G_{n} = 1

$G_n=1$ , Из теоремы об орбите-стабилизаторе следует, что

| G_{1} : G_{2} | \leq k

$|G_1:G_2|\leq k$ , а также

| G_{i} : G_{i + 1} | \leq k - 1

$|G_i:G_{i+1}|\leq k-1$ за

i \in {2, \dots, n - 1}

$i\in\{2,\ldots,n-1\}$ ,

Верет

Число автоморфизмов графа для графа изоморфизма

Ответы: