# Classify the isomorphism of a graph

• I
• fiksx
In summary, N and k are positive integers satisfying 1<=k<n. An undirected graph G_{n,k} is defined where V_{n,k} = {1,2,3,...n} and E_{n,k} = {\{\{u,v\}|u-v \equiv k \, (mod \, n) \, or \, u-v \equiv -k \, mod \, n}. The graph is classified by all k that are isomorphic to each other for G_{16,k} (1<=k<=15). The isomorphism classes for G_{5,k} are {1,2,3,4,5} and {1,3,5,7,9
fiksx
TL;DR Summary
classify isomoprhism of graph
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 think I follow you right up to this statement:
fiksx said:
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 : fiksx said:$$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. tnich said: 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 fiksx said: 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?

## 1. What is an isomorphism in graph theory?

An isomorphism in graph theory is a mapping between two graphs that preserves the structure and connectivity of the vertices and edges. This means that if two graphs are isomorphic, they will have the same number of vertices and edges, and the same pattern of connections between them.

## 2. How do you classify the isomorphism of a graph?

To classify the isomorphism of a graph, you need to compare it to other graphs and determine if there is a mapping that preserves the structure and connectivity. This can be done by visually inspecting the graphs or by using mathematical algorithms.

## 3. What is the importance of classifying isomorphism in graph theory?

The classification of isomorphism is important because it allows us to identify and group graphs that have similar properties and structures. This can help us understand the relationships between different graphs and solve complex problems more efficiently.

## 4. Can two non-isomorphic graphs have the same number of vertices and edges?

Yes, it is possible for two non-isomorphic graphs to have the same number of vertices and edges. Isomorphism is not determined solely by the number of vertices and edges, but also by the pattern of connections between them.

## 5. Are there any real-world applications of isomorphism in graph theory?

Yes, isomorphism in graph theory has many real-world applications, such as in computer science for data compression and cryptography, in chemistry for understanding molecular structures, and in social networks for identifying patterns of connections between individuals.

• General Math
Replies
6
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
• General Math
Replies
1
Views
3K
• Introductory Physics Homework Help
Replies
1
Views
599
• Mechanics
Replies
1
Views
1K
• General Math
Replies
1
Views
4K
• Precalculus Mathematics Homework Help
Replies
12
Views
3K
• Math Proof Training and Practice
Replies
100
Views
8K
• Math Proof Training and Practice
Replies
61
Views
6K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K