About searching for antipodal vertexes in symmetric Cayley graphs

I. M. Khuziev

Moscow Institute of Physics and Technology, 5/2 Pervomaiskaya St., 141700 Dolgoprudnyi, Russia

Abstract: We present the antipodality relation and search for an antipodal vertex. We also give a randomized algorithm solving the oracle problem in symmetric Cayley graphs over group $\mathbb Z_2^n$. The number of queries is polynomial over the graph's degree. Ill. 1, bibliogr. 5.

Keywords: graph, automorphism, antipodality, oracle.

UDC: 519.178

Received: 03.03.2014
Revised: 26.08.2014

DOI: 10.17377/daio.2015.22.443

 English version: Journal of Applied and Industrial Mathematics, 2015, 9:2, 206–214

Bibliographic databases:

• 
•