# Questions tagged [graph-isomorphism]

Two graphs $G$ and $H$ are isomorphic if they have a function $f$ which provides an exact pairing of vertices in the two graphs such that for any adjacent vertices $u,v\in \{\mbox{set of vertices of }G\}$, $f(u)$ and $f(v)$ are also adjacent in $H$.

277 questions
1answer
18 views

### Non-isomorphic graphs with same Tutte polynomial

I've been looking for some non-isomorphic graphs with the same Tutte polynomial. I'm aware of this thread and this thread, however my understanding of matroids is non-existent, and they are a bit ...
1answer
21 views

### Cospectral graphs that are non-isomorphic and that only have simple eigenvalues

It is a well known fact that there are non-isomorphic connected graphs whose adjacency matrix have the same spectrum. This has been discussed, for example, in this older post. However, in the ...
1answer
34 views

### If $G$ and $H$ on 3 or more vertices are hypomorphic, don't they have to be isomorphic due to their shared induced subgraphs?

Basically, my reasoning is that any two finite graphs with at least three vertices will have at least three vertex-deleted subgraphs, which are also induced subgraphs. Any two graphs which share at ...
1answer
32 views

### Expanding definition of simple graph isomorphism to include multigraphs

I've defined isomorphism from one graph $G$ to another graph $K$ as follows: An isomorphism is a bijective function $f$ from the vertices of $G$ to the vertices of $K$, such that the vertices $u$ and ...
1answer
34 views

### Prove that two graphs are isomorphic

I just found an old book about number theory and graph theory I used on my first course at university many years ago. Looking inside it, I found a handwritten note pointing to a problem that says: ...
1answer
45 views

### Prove that if two graphs, $G$ and $\overline{G}$, are isomorphic, the number of nodes cannot be twice an odd number.

Having a really hard time going about proving this. First, Graph $G$ is constructed by having $n$ nodes and joining some pairs of distinct nodes with at most one line. Second, Graph $\overline{G}$ ...
0answers
29 views

### Let $G,G'$ be two digraphs, show that $\phi^{-1}$ is an isomorphism

Problem So let $\phi : G \rightarrow G'$ be an isomorphism between two directed graphs. Prove that $\phi^{-1}$ is an isomorphism. Also prove if $H \leq Aut(G')$ then $\phi^{-1}H\phi\leq Aut(G)$. My ...
6answers
2k views

### Are these two graphs isomorphic? Why/Why not?

Are these two graphs isomorphic? According to Bruce Schneier: "A graph is a network of lines connecting different points. If two graphs are identical except for the names of the points, they are ...
0answers
32 views

### What is the current fastest algorithm for finding the maximum common subgraph?

First of all, it's my first time at this sub StackExchange so, my apologies if I'm making some newbie mistake when asking this question. I'm currently researching algorithms for finding the maximum ...
1answer
33 views

1answer
102 views

### Number of isomorphisms between two graphs

I'm studying for an exam in graph theory, and this question came up. The question is: how many isomorphisms exist between these two graphs. I know that, as they are isomorphic, this is the same as ...
1answer
51 views

### Prove that the graphs $G$ and $H$ are not isomorphic

Let $G$ be the graph on the left and $H$ be the graph on the right. For $G$: number of edges: $9$ number of vertices: $6$ degree sequence: $3,3,3,3,3,3$ For $H$: number of edges: $9$ number of ...
1answer
28 views

### Are G and H necessarily isomorphic?

Let $G$ and $H$ be two simple graphs, both of them with seven vertices, each of which is of degree 2. Are G and H necessarily isomorphic? The graphs $G$ and $H$ must have a cycle since each vertex is ...
1answer
81 views

### Isomorphism in regular graphs

Let $G$ be a connected regular graph. Consider two different vertices $u,v$ of $G$. Let $H_1$ be the graph obtained from $G$ by deleting vertex $u$, and $H_2$ be the graph obtained from $G$ by ...
1answer
58 views

### Testing if two matrices differ only by permutation? (generalized graph isomorphism problem)

In graph isomorphism problem, for which Babai's quasi polynomial algorithm is currently under review (stack), we ask if two adjacency matrices: of $\{0,1\}$ coefficients differ only by a permutation. ...
0answers
707 views

### Testing if two finite sets of points differ only by rotation (unordered, in polynomial time in size and dimension)?

Imagine we have two size $m$ sets (without order) of points $X=\{x^i\}_{i=1..m}, Y=\{y^i\}_{i=1..m} \subset \mathbb{R}^n$ and we want to answer the question if they differ only by rotation: if there ...
1answer
36 views

### Question about Lemma on Primitive Groups

I am reading the following lemma in a paper about graph isomorphism: Lemma: Let P be a transitive p-subgroup of Sym(A) with |A| > 1. Then any minimal p-block system consists of exactly p blocks. ...
1answer
33 views

### GI-Completeness of graph isomorphism with connected graphs

The Wikipedia page for Graph Isomorphism lists connected graphs as GI-complete. The citation has a paywall, and I have not been able to find any NP-complete algorithms for isomorphism of connected ...
2answers
100 views

### Determine which pairs of graphs below are isomorphic.

I've managed to show that $A \ncong C$, since $A$ doesn't has a 4-cycle, and $C$ does. Likewise I suspect that $B \ncong C$, but this is just by inspection. Any other observation?
2answers
116 views

### Find a self-complementary graph with $v = 8$. Of the $12, 346$ graphs with $v = 8$ only four are self-complementary.

This is Trudeau's exercise 2.16: Find a self-complementary graph with $v = 8$. Of the $12, 346$ graphs with $v = 8$ only four are self-complementary. The picture in below is the answer that the book ...
0answers
37 views

### Computational Treatment: Relational Isomorphism Problem

We consider relational systems $(X_1,Y_1,R_1)$ and $(X_2,Y_2,R_2)$ with $R_i\subseteq X_i\times Y_i$. An isomorphism is a pair of bijective maps $(\alpha,\beta)$, with $\alpha: X_1\rightarrow X_2$ and ...
0answers
24 views

### Formula to convert a point on graph A to a point on graph B

I already asked a similar question, but I found more information that makes my previous one invalid. If I had the following graphs (ignore the poor quality): graph A (https://imgur.com/a/jd7QMSQ) ...
0answers
105 views

### Prove that the Chromatic Number is Invariant under Isomorphism

I have a "Which of the following graphs are isomorphic?" question. The graphs are the same order and regular, which makes it quite difficult for me to prove why they are isomorphic, or find out why ...
0answers
42 views

### Isomorphism of circulant graphs

Can circulant graphs be isomorphic to any non-circulant regular graph? I am trying to show uniqueness of a graph for a given independence polynomial and the graph I obtained is a circulant graph on 9 ...
0answers
23 views