Lesson plan

Local complementation

In graph theory, local complementation (also known as vertex inversion) is an operation on a graph that toggles adjacencies among the neighbours of a chosen vertex, while all other adjacencies remain unchanged. Despite its simple definition, it preserves interesting properties and generates a complex equivalence relation. The operation was introduced by Anton Kotzig and later studied in depth by André Bouchet and Von-Der-Flaass. Formally, the local complementation of a simple undirected graph G at a vertex v is an operation that produces a new graph, denoted by G \star v . This operation is defined by replacing the subgraph of G induced by N_G(v) with its complementary subgraph. In other words, two distinct vertices x and y are adjacent in the graph G \star v when exactly one of the following holds: # vertices x and y are adjacent in G ; or # both vertices x and y are neighbours of v in G . Two graphs are said to be locally equivalent if one can be obtained from the other through a sequence of local complementations. This defines an equivalence relation on graphs, whose equivalence classes are known as local equivalence classes. For example, the star graph and complete graph on n vertices are locally equivalent, and they form a local equivalence class. The local equivalence classes on graphs with up to 12 vertices has been computed.…

Back to article

Article summary

In graph theory, local complementation (also known as vertex inversion) is an operation on a graph that toggles adjacencies among the neighbours of a chosen vertex, while all other adjacencies remain unchanged. Despite its simple definition, it preserves interesting properties and generates a complex equivalence relation. The operation was introduced by Anton Kotzig and later studied in depth by André Bouchet and Von-Der-Flaass. Formally, the local complementation of a simple undirected graph G at a vertex v is an operation that produces a new graph, denoted by G \star v . This operation is defined by replacing the subgraph of G induced by N_G(v) with its complementary subgraph. In other words, two distinct vertices x and y are adjacent in the graph G \star v when exactly one of the following holds: # vertices x and y are adjacent in G ; or # both vertices x and y are neighbours of v in G . Two graphs are said to be locally equivalent if one can be obtained from the other through a sequence of local complementations. This defines an equivalence relation on graphs, whose equivalence classes are known as local equivalence classes. For example, the star graph and complete graph on n vertices are locally equivalent, and they form a local equivalence class. The local equivalence classes on graphs with up to 12 vertices has been computed.…

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.