Classify the isomorphism of a graph

73
1

Summary:

classify isomoprhism of graph

Main Question or Discussion Point

N and k are positive integers satisfying $$ 1<=k < n$$

An undirected graph $$G_{n,k}= (V_{n,k} ,E_{n,k})$$ is defined as follows.

$$V_{n,k}={1,2,3,...n}$$

$$E_{n,k}={\{\{u,v\}|u-v \equiv k \, (mod \, n) \, or \, u-v \equiv -k \, mod \, n}$$

However, $$x \equiv y \, (mod \, n) $$ indicates that x and y are congruent modulo n. For example, $$12 \equiv 5 \equiv -2 (mod 7)$$

i need to Classify graph G by all k that is isomorphism to each other for $$G_{16,k} (1<=k<=15) $$ Example {1,2},{3},{4,5,6}


my attempt:
$$G_{16,k} (1<=k<=15) $$
Classify graph G by all k that is isomorphism
Example {1,2},{3},{4,5,6}

I see that by definition for example $$G_{5,1}$$
we can see that

$$V={1,2,3,4,5}$$

Since $$ 6 \equiv 1 \equiv -4 \, mod \, 5$$ we know that


$$E=\{(1,5),(5,4),(4,3),(3,2),(2,1) \} $$

But how can i classify k that isomorphism to each other for $$G_{16,k}$$

I thought that $$\{2,4,6,8,10,12,14,16 \} $$ and $$\{1,3,5,7,9,11,13,15 \} $$ will be isomorphism to each other, am i right?

i.e $$G_{2,4} \& G_{4,6}$$ will have same vertex and degree(?)
 

Answers and Replies

tnich
Homework Helper
1,048
336
I think I follow you right up to this statement:
I thought that ##\{2,4,6,8,10,12,14,16 \} ## and $$\{1,3,5,7,9,11,13,15 \} ## will be isomorphism to each other, am i right?
It is true, that these two sets of vertices would form isomorphic graphs if they were connected by edges in the same way, but neither one of the these seems to be a ##G_{n,k}## graph according to your definition. I suggest that you start with say 4 vertices and draw all of the ##G_{4,k}## graphs for ##k=-5, \dots , 6## according to this rule :
$$E_{n,k}={\{\{u,v\}|u-v \equiv k \, (mod \, n) \, or \, u-v \equiv -k \, mod \, n}$$
That is, draw four vertices on a piece of paper, set k = -5, look at each vertex in turn and draw an edge from it to each vertex with a label that differs by ##\pm 5 \mod 4##. Then do it again for ##k=-4## and so on. Then eyeball your graphs to identify the sets of isomorphic graphs. That should give you feeling for how to write a general solution.
 
73
1
I think I follow you right up to this statement:

It is true, that these two sets of vertices would form isomorphic graphs if they were connected by edges in the same way, but neither one of the these seems to be a ##G_{n,k}## graph according to your definition. I suggest that you start with say 4 vertices and draw all of the ##G_{4,k}## graphs for ##k=-5, \dots , 6## according to this rule :

That is, draw four vertices on a piece of paper, set k = -5, look at each vertex in turn and draw an edge from it to each vertex with a label that differs by ##\pm 5 \mod 4##. Then do it again for ##k=-4## and so on. Then eyeball your graphs to identify the sets of isomorphic graphs. That should give you feeling for how to write a general solution.
thankyou for answering my questions! i think this has relation to equivalence class such as {8,16},{7,9},{6,10},{5,11},{4,12},{3,13},{14,2},{15,1} for example for k=1 $$ 1≡-15 mod 16$$ and k=15 $$15≡−1 mod16 $$ is in same class so it is isomorphism as it will have same edge and vertex , is my reasoning right?
 
tnich
Homework Helper
1,048
336
thankyou for answering my questions! i think this has relation to equivalence class such as {8,16},{7,9},{6,10},{5,11},{4,12},{3,13},{14,2},{15,1} for example for k=1 $$ 1≡-15 mod 16$$ and k=15 $$15≡−1 mod16 $$ is in same class so it is isomorphism as it will have same edge and vertex , is my reasoning right?
Yes (except that I don't understand why you include {8,16}).
Now look at ##G_{5,k}##. What are the isomorphism classes?
 

Related Threads for: Classify the isomorphism of a graph

  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
1
Views
1K
Replies
3
Views
418
Replies
4
Views
9K
Replies
5
Views
3K
Replies
3
Views
2K
Top