Jumlah Automorfisme dari grafik untuk isomorfisme grafik

Misalkan $G$ dan $H$ menjadi dua grafik ukuran- $r$ terhubung secara teratur $n$ . Biarkan $A$ adalah himpunan permutasi $P$ sehingga $PGP^{-1}=H$ . Jika $G=H$ maka $A$ adalah himpunan automorphisms dari $G$ .

Apa batas atas yang paling dikenal pada ukuran $A$ ?
Apakah ada hasil untuk kelas grafik tertentu (tidak mengandung grafik siklus lengkap)?

Catatan: Membangun kelompok automorfisme setidaknya sama sulitnya (dalam hal kompleksitas komputasinya) dengan memecahkan masalah grafik isomorfisme. Bahkan, hanya menghitung automorfisme adalah polinomial-waktu yang setara dengan grafik isomorfisme, cf R. Mathon, "Catatan pada grafik masalah menghitung isomorfisme".

reference-request graph-theory co.combinatorics graph-isomorphism gr.group-theory Jim
sumber

$G$ $3$ $G$ $3n\cdot 2^n$ $3$ $k$

$F$ $n$ $\mod k$ $k$ $G(F)$ $O(k^2\cdot n)$ $F$ $G(F)$ $k^n$ $k$

Mateus de Oliveira Oliveira
sumber

Harap perhatikan grafik berikut, 1. grafik reguler dan grafik reguler (tidak ada satupun yang lengkap atau grafik siklus) yang digabungkan satu sama lain melalui E jumlah tepi, katakanlah grafik yang digabungkan ini adalah grafik tidak teratur 2. setiap simpul dari grafik biasa memiliki tepi dengan grafik biasa . Tidak ada dua simpul grafik biasa , yang memiliki jumlah sisi yang sama dengan grafik biasa . Bisakah automorfisme G menjadi eksponensial?

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

Iya. Grafik G2 dapat memiliki jumlah otomorfisma yang eksponensial. Biarkan H1 menjadi grafik biasa r1 dengan n simpul, bernomor 1 ... n.Biarkan H2 menjadi grafik yang diperoleh dengan proses berikut (dibagi menjadi 3 komentar). Misalkan D adalah grafik intan, yaitu siklus 4 bersama dengan tepi yang menghubungkan dua simpul yang sebelumnya tidak berdekatan. Katakanlah bahwa dua simpul ini adalah simpul internal D. Dua simpul lainnya adalah simpul eksternal D. Jelas, ada automorhpisme yang menukar kedua simpul internal dan membiarkan simpul eksternal tersentuh.

Mateus de Oliveira Oliveira

Sekarang, pertimbangkan penyatuan dua siklus C1 dan C2 dengan simpul n (n + 1) / 2 yang dinomori dari 1 ke n (n + 1) / 2. Juga pertimbangkan n (n + 1) / 2 salinan grafik diamod. Sekarang untuk setiap i, hubungkan salah satu vertek eksternal D_i ke vertex ke-1 C1 dan vertex eksternal lainnya ke vertex ke-ke-C2. Kemudian grafik H2 yang diperoleh oleh proses ini adalah 3-reguler, dan memiliki jumlah otomorpisme eksponensial, karena simpul internal masing-masing D_i dapat ditukar secara terpisah.

Mateus de Oliveira Oliveira

Sekarang untuk setiap vertex v_j dari H1 kami menambahkan tepi 2j dari v_j ke simpul internal berlian sedemikian rupa sehingga kedua simpul internal berlian D_i terhubung ke simpul yang sama di H1. Ini menjamin bahwa simpul-simpul internal intan masih dapat ditukar, dan karenanya jumlah total automorfisme dalam grafik G2 bersifat eksponensial.

Mateus de Oliveira Oliveira

Sangat mudah untuk menunjukkan bahwa graf terhubung order dan maksimal valensi memiliki kelompok automorphism pesanan paling . Temukan urutan simpul sedemikian rupa sehingga, dimulai dengan yang kedua, setiap simpul berdekatan dengan setidaknya satu simpul yang datang sebelumnya. Biarkan menjadi subkelompok yang memperbaiki simpul pertama . Ini adalah rantai subkelompok turun, dengan dan . Ini diikuti oleh teorema penstabil orbit yang , dan untuk .

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

Jumlah Automorfisme dari grafik untuk isomorfisme grafik

Jawaban: