Mathematics – Combinatorics
Scientific paper
2007-02-09
Mathematics
Combinatorics
22 pages, no figure, more clear presentation and minor errors fixed
Scientific paper
There are local operators on (labeled) graphs $G$ with labels $(g_{ij})$ 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\in \mathbf{F}_q$, the finite field of $q$ elements. The operator is to obtain a graph with labels $g'_{ij}=g_{ij}+ag_{vi}g_{vj}$. For the second type of operators, let $0\neq b\in \mathbf{F}_q$ and the resulted graph is a graph with labels $g''_{vi}=bg_{vi}$ and $g''_{ij}=g_{ij}$, 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 $q^{2n+1}$, and consequently, the number of classes of local equivalency is $q^{\frac{n^2}{2}-o(n)}$.
Bahramgiri Mohsen
Beigi Salman
No associations
LandOfFree
Enumerating the Classes of Local Equivalency in Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Enumerating the Classes of Local Equivalency in Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enumerating the Classes of Local Equivalency in Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-8420