Abstract | ||
---|---|---|
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 gij = gij +agvigvj. For the second, if 0 6= 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 complemen- tations has been studied, (3). 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. |
Year | Venue | Keywords |
---|---|---|
2007 | Clinical Orthopaedics and Related Research | data structure,finite field |
Field | DocType | Volume |
Discrete mathematics,Graph,Combinatorics,Finite field,Vertex (geometry),Algorithm,Operator (computer programming),Mathematics,Binary number | Journal | abs/cs/070 |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mohsen Bahramgiri | 1 | 106 | 6.21 |
Salman Beigi | 2 | 56 | 11.43 |