2007/02/09 by Mohsen Bahramgiri, Bahramgiri, Mohsen, Salman Beigi +1 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.math/0702267
22 pages, no figure, more clear presentation and minor errors fixed
arxiv created 2007/07/04 · arxiv updated 2009/12/01
There are local operators on (labeled) graphs G with labels (gij) coming from a finite field. If the filed is binary, in other words, if the graph is ordinary, the operation is just the local complementation. That is, to choose a vertex and complement the subgraph induced by its neighbors. But, in the general case, there are two different types of operators. The first type is the following. Let v be a vertex of the graph and a∈ Fq, the finite field of q elements. The operator is to obtain a graph with labels g'ij=gij+agvigvj. For the second type of operators, let 0≠ b∈ Fq and the resulted graph is a graph with labels g''vi=bgvi and g''ij=gij, for i,j unequal to v. The local complementation operator (binary case) has appeared in combinatorial theory, and its properties have studied in the literature. Recently, a profound relation between local operators on graphs and quantum stabilizer codes has been found, and it has become a natural question to recognize equivalency classes under these operators. In the present article, we show that the number of graphs locally equivalent to a given graph is at most q2n+1, and consequently, the number of classes of local equivalency is q(n2)/(2)-o(n).