2007/02/09 by Mohsen Bahramgiri, Bahramgiri, Mohsen, Salman Beigi +1 · 1 citation
Computer Science · Engineering · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Graph theory and applications #cs.DS #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.cs/0702057
21 pages, no figures, minor corrections
openalex publication_date 2007/02/09 · arxiv created 2007/07/01 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let v be a vertex of a graph G. By the local complementation of G at v we mean to complement the subgraph induced by the neighbors of v. This operator can be generalized as follows. Assume that, each edge of G has a label in the finite field Fq. Let (gij) be set of labels (gij is the label of edge ij). We define two types of operators. For the first one, let v be a vertex of G and a∈ Fq, and obtain the graph with labels g'ij=gij+agvigvj. For the second, if 0≠ b∈ Fq the resulted graph is a graph with labels g''vi=bgvi and g''ij=gij, for i,j unequal to v. It is clear that if the field is binary, the operators are just local complementations that we described. The problem of whether two graphs are equivalent under local complementations has been studied, \citebouchalg. Here we consider the general case and assuming that q is odd, present the first known efficient algorithm to verify whether two graphs are locally equivalent or not.