# Finding Self Isomorphisms in Graphs

• scorpius1782
In summary, the conversation discusses finding non-trivial self isomorphisms in a given graph, with non-trivial meaning at least one node is not mapped onto itself. The speaker is confused about the concept of self-isomorphism and wonders if they should split the graph and look for two isomorphic graphs. They seek clarification, and it is suggested that a non-trivial isomorphism would preserve edge structure but not necessarily the shape of the graph. The conversation ends with the speaker thanking the other person and mentioning that they will read up on the concept of automorphism.
scorpius1782

## Homework Statement

I'm given a graph and am told to find non-trivial self isomorphisms. Non-trivial meaning that at least 1 node is "not mapped onto itself."

I've tried looking for self isomorphism but I can't find anything. I can tell when two graphs are isomorphic through inspection but "self-isomorphism" doesn't make any sense to me. Does this mean I'm suppose to split the graph and find a two that are isomorphic? So cut a whole bunch of edges and see if I can make two isomorphic graphs??

I'm just looking for clarity.

Thanks.

scorpius1782 said:

## Homework Statement

I'm given a graph and am told to find non-trivial self isomorphisms. Non-trivial meaning that at least 1 node is "not mapped onto itself."

I've tried looking for self isomorphism but I can't find anything. I can tell when two graphs are isomorphic through inspection but "self-isomorphism" doesn't make any sense to me. Does this mean I'm suppose to split the graph and find a two that are isomorphic? So cut a whole bunch of edges and see if I can make two isomorphic graphs??

I'm just looking for clarity.

Thanks.

I believe a trivial isomorphism ##\phi## of a graph ##G## to another graph ##H## is an automorphism. For example, consider the identity map, which maps every node and edge onto itself (so really the graph wouldn't change at all, i.e ##G = H##).

I think a non-trivial isomorphism would map the vertices in ##G## onto ##H##, preserving edge structure, but not necessarily the shape of the graph.

1 person
automorphism- Word I was looking for I guess. I'll be reading up on this. Thank you.

Edit: All wrong, figured it out with help from TA.

#### Attachments

• graph.jpg
8.6 KB · Views: 425
Last edited:

## 1. What is a self isomorphism in graphs?

A self isomorphism in graphs is a mapping that preserves the structure of a graph, meaning that the graph remains unchanged after the mapping is applied. In other words, the graph is isomorphic to itself.

## 2. How do you find self isomorphisms in a graph?

To find self isomorphisms in a graph, you can use an algorithm such as the VF2 algorithm or the Nauty algorithm. These algorithms compare the structure of the graph to itself and identify mappings that preserve the structure.

## 3. Why is finding self isomorphisms in graphs important?

Finding self isomorphisms in graphs can help in identifying important properties of the graph, such as symmetries and automorphisms. It can also be used in graph theory and computer science for tasks such as graph matching and graph compression.

## 4. Are there any real-world applications of self isomorphisms in graphs?

Yes, self isomorphisms in graphs have various real-world applications. For example, they are used in chemistry to identify symmetries in molecules, in image processing for pattern recognition, and in data mining for identifying similar structures in large datasets.

## 5. Can self isomorphisms be found in any type of graph?

Yes, self isomorphisms can be found in any type of graph, including directed and undirected graphs, weighted and unweighted graphs, and even disconnected graphs. However, the complexity of finding self isomorphisms may vary depending on the type and size of the graph.

Replies
1
Views
1K
Replies
11
Views
2K
Replies
5
Views
2K
Replies
4
Views
6K
Replies
5
Views
3K
Replies
6
Views
2K
Replies
3
Views
2K
Replies
11
Views
2K
Replies
3
Views
2K
Replies
6
Views
2K