0
$\begingroup$

If i have a graph in this form (adjacency matrix):

0 0 1 0 0 0 1
0 0 0 1 0 1 0
1 0 0 1 0 0 0
0 1 1 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 1 0 0
1 0 0 0 1 0 0

This is a 2-regular graph with 7 vertices. What are examples of vertex invariants? Usually i would look at the degrees of each vertex, but they are all the same in this case.

  • 0
    What is a vertex invariant? Do you mean graph invariant? Could you be a little more specific about what it is you are looking for?2010-12-14

1 Answers 1

4

2-regular (simple) graphs on n vertices are determined (up to isomorphism) by the partition of n induced by the size of its connected components. This is because connected components of 2-regular graphs must be cycles.

Conversely, given a partition $d_1,d_2,\ldots,d_k$ of n into parts of size at least 3 (you can't have cycles of length 1 or 2, which would induce loops and multiedges) then you can construct a 2-regular graph consisting of a $d_i$-cycle for each $d_i$.

In the above case, the partition is 7 (since the graph is a 7-cycle).

0 0 1 0 0 0 1
0 0 0 1 0 1 0
1 0 0 1 0 0 0
0 1 1 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 1 0 0
1 0 0 0 1 0 0

There exist an automorphism of the graph that maps vertex u to vertex v provided u and v both belong to cycles of the same length. To illustrate, you can fix everything outside of the components containing u and v, then

  • if u and v are in the same cycle, just rotate the cycle, or otherwise,
  • swap the cycles containing u and v, then rotate each appropriately.