Saya tidak memiliki pengetahuan di bidang teori kompleksitas yang melibatkan kelompok, jadi saya minta maaf jika ini adalah hasil yang diketahui.
Pertanyaan 1. Biarkan menjadi grafik pesanan sederhana yang tidak diarahkan n . Apa kompleksitas komputasi (dalam hal n ) untuk menentukan apakah G adalah verteks-transitif?
Ingat bahwa grafik adalah titik-transitif jika A u t ( G ) bertindak transitif pada V ( G ) .
Saya tidak yakin jika definisi di atas memungkinkan untuk algoritma waktu polinomial karena dapat bahwa urutan adalah eksponensial.
Namun grafik vertex-transitif memiliki beberapa sifat struktural lain yang mungkin dieksploitasi agar dapat menentukannya secara efisien, jadi saya tidak yakin apa status dari pertanyaan di atas.
Subkelas lain yang menarik dari grafik vertex-transitive yang memiliki struktur lebih banyak lagi adalah kelas grafik Cayley . Jadi wajar juga jika mengajukan pertanyaan terkait berikut
Pertanyaan 2. Apa kompleksitas komputasi dalam menentukan apakah grafik adalah grafik Cayley?
Jawaban:
Saya tidak punya jawaban yang lengkap, tetapi saya pikir kedua masalah itu terbuka.
Makalah karya Jajcay, Malnič, Marušič [3] terkait dengan pertanyaan pertama Anda. Mereka menyediakan beberapa alat untuk menguji transitex verteks. Mereka mengatakan dalam pendahuluan bahwa:
Perhatikan bahwa uji transit-simpul dapat dilakukan dengan menguji grafik isomorfisme kali. Buatlah dua salinan G dan G ' dari grafik Anda, dengan jangkar khusus (seperti jalan panjang n + 1 ) di u ∈ V ( G ) dan v ∈ V ( G ' ) . Ada isomorfisme antara G dan G ′ jika dan hanya jika grafik asli memiliki pemetaan automorfisme u ke v . Dengan demikian Anda dapat menguji verteks-tansitivity dengan memperbaiki vertexn−1 G G′ n+1 u∈V(G) v∈V(G′) G G′ u v x , dan memeriksa bahwa ada pemetaan automorfisme x ke semua simpul lainnya.
Perhatikan juga bahwa jika uji transeksif verteks dapat dilakukan dalam waktu polinomial, maka uji isomorfisme untuk grafik transeks-verteks. Ini karena dua grafik verteks-transitif adalah isomorfik jika dan hanya jika persatuan terpisahkan mereka adalah transeks-verteks. Saya percaya bahwa kompleksitas isomorfisme grafik untuk grafik vertex-transitif tidak diketahui.
Untuk pertanyaan ke-2, saya menemukan hasil parsial. Sebuah grafik circulant adalah grafik Cayley pada sekelompok siklik. Evdokimov dan Ponomarenko [2] menunjukkan bahwa pengenalan grafik peredaran dapat dilakukan dalam waktu polinomial. Juga bab buku karya Alspach [1, Bab 6: Grafik Cayley, Bagian 6.2: Pengakuan] akan menarik bagi Anda, meskipun dikatakan bahwa:
sumber