Liczba automorfizmów wykresu dla izomorfizmu grafowego

Niech i będą dwoma połączonymi wykresami regularnymi o rozmiarze . Niech być zbiorem permutacji tak, że . Jeśli następnie jest zestaw automorfizmy o . $G$ $H$ $r$ $n$ $A$ $P$ $PGP^{-1}=H$ $G=H$ $A$ $G$

Jaka jest najbardziej znana górna granica rozmiaru ? Czy są jakieś wyniki dla poszczególnych klas grafów (niezawierających grafów kompletnych / cyklicznych)? $A$

Uwaga: Skonstruowanie grupy automorfizmów jest co najmniej tak samo trudne (pod względem złożoności obliczeniowej), jak rozwiązanie problemu izomorfizmu grafów. W rzeczywistości samo liczenie automorfizmów jest równoznaczne z czasem wielomianowym równoważnym z izomorfizmem grafowym, por. R. Mathon, „Uwaga na temat problemu zliczania izomorfizmów grafowych”.

reference-request graph-theory co.combinatorics graph-isomorphism gr.group-theory Jim
źródło

Wormald pokazał, że jeśli jest połączonym nieregularnym wykresem z 2n wierzchołkami, to liczba automorfizmów dzieli . W szczególności daje to nietrywialną wykładniczą górną granicę dla przypadku regularnego. Być może w tym wierszu są wyniki dla ogólnych wykresów nieregularnych. $G$ $3$ $G$ $3n\cdot 2^n$ $3$ $k$

Dla dolnej granicy rozważmy wzór z wejściami, których bramkami są dodawanie bramki wachlarza 2. Następnie za pomocą resut Torana można skonstruować -wykres regularny z wierzchołki których grupa automorfizmem koduje wszystkie możliwe oceny . Oznacza to, że liczba automorfizmów wynosi co najmniej . Pokazuje to, że istnieje wykładnicza dolna granica liczby automorfizmów wykresów regularnych w zależności od ich liczby wierzchołków. $F$ $n$ $\mod k$ $k$ $G(F)$ $O(k^2\cdot n)$ $F$ $G(F)$ $k^n$ $k$

Mateus de Oliveira Oliveira
źródło

Proszę wziąć pod uwagę następujący wykres: 1. regularny i wykres regularny (żaden z nich nie jest kompletny ani cykliczny) są połączone ze sobą poprzez E liczbę krawędzi, powiedzmy, że ten połączony wykres jest nieregularnym wykresem 2. każdy wierzchołek wykres ma krawędzie z regularnym wykresem . Nie ma dwóch wierzchołków zwykłego wykresu , które mają taką samą liczbę krawędzi zwykły wykres . Czy automorfizm G może być wykładniczy?

r_{1}

$r_1$

r_{2}

$r_2$

G

$G$

r_{1}

$r_1$

r_{2}

$r_2$

r_{1}

$r_1$

r_{2}

$r_2$

Jim,

tak. Wykres G2 może mieć wykładniczą liczbę automorfizmów. Niech H1 będzie dowolnym regularnym wykresem r1 z n wierzchołkami, ponumerowanymi 1 ... n. Niech H2 będzie wykresem otrzymanym w następującym procesie (podzielonym na 3 komentarze). Niech D będzie wykresem diamentowym, tj. 4-cyklowym wraz z krawędzią łączącą dwa wcześniej niesąsiadujące wierzchołki. Powiedzmy, że te dwa wierzchołki są wewnętrznymi wierzchołkami D. Pozostałe dwa wierzchołki są zewnętrznymi wierzchołkami D. Oczywiście, istnieje automorfizm, który zamienia oba wewnętrzne wierzchołki i pozostawia zewnętrzne wierzchołki nietknięte.

Mateus de Oliveira Oliveira

Rozważmy teraz rozłączny związek dwóch cykli C1 i C2 z n (n + 1) / 2 wierzchołkami ponumerowanymi od 1 do n (n + 1) / 2. Weź również pod uwagę n (n + 1) / 2 kopie wykresu diamod. Teraz dla każdego i połącz jeden z zewnętrznych wierzchołków D_i z i-tym wierzchołkiem C1, a drugi zewnętrzny wierzchołek z i-tym wierzchołkiem C2. Następnie wykres H2 otrzymany w tym procesie jest 3-regularny i ma wykładniczą liczbę automorfizmów, ponieważ wewnętrzne wierzchołki każdego D_i można zamieniać osobno.

Mateus de Oliveira Oliveira

Teraz dla każdego wierzchołka v_j H1 dodajemy krawędzie 2j od v_j do wewnętrznych wierzchołków diamentów w taki sposób, że oba wewnętrzne wierzchołki diamentu D_i zostają połączone z tym samym wierzchołkiem w H1. Gwarantuje to, że wewnętrzne wierzchołki diamentu można nadal zamieniać, a zatem całkowita liczba automorfizmów na wykresie G2 jest wykładnicza.

Mateus de Oliveira Oliveira

Łatwo wykazać, że połączony wykres rzędu i maksymalnej wartościowości ma grupę automorfizmu rzędu co najwyżej . Znajdź kolejność wierzchołków w taki sposób, że zaczynając od drugiego, każdy wierzchołek sąsiaduje z co najmniej jednym wierzchołkiem, który pojawił się wcześniej. Niech będzie podgrupą ustalającą pierwsze wierzchołki. Jest to malejący łańcuch podgrup, z i . Następnie następuje twierdzenie o stabilizacji orbity, że , i dla .

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\}$

verret

Liczba automorfizmów wykresu dla izomorfizmu grafowego

Odpowiedzi: