# Classify the isomorphism of a graph

• I

## 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(?)

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. 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 tnich Homework Helper 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?