Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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? –  user4143 Dec 14 '10 at 21:42
add comment

1 Answer

up vote 4 down vote accepted

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.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.