Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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$.

0
votes
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 ...
1
vote
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 ...
2
votes
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 ...
1
vote
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 ...
2
votes
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: ...
2
votes
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}$ ...
0
votes
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 ...
6
votes
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 ...
1
vote
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 ...
0
votes
1answer
33 views

Number of non-isomorphic 2-factors of $K_n$

Let $f(n,k)$ be the number of non-isomorphic 2-factors of $K_n$ containing exactly k components. Explain why the recurrence relation $$ f(n,k) =f(n-3,k-1)+f(n-k,k)$$ holds for $n \geq 4 $ and $1 \...
3
votes
1answer
61 views

How can I show that there will be at most $4^{n+1}$ pairwise non-isomorphic trees on $n+1$ vertices?

Prove that there exist at most $4^n$ pairwise non-isomorphic trees on $n$ vertices. I proceed by Induction, Let $n=1$ then we have only one tree on $1$ vertex which is less than $4$. Now assume ...
1
vote
1answer
141 views

The number of non-isomorphic subgraphs of K3 is only 7

This comes from a book called Introduction to Graph Theory (Dover Books on Mathematics) at the end of the first chapter we are asked to draw all 17 subgraphs of k3 which is pretty easy to do. however ...
1
vote
0answers
64 views

Measure of subgraph isomorphisms

I have a "big" (biological) finite graph $\Gamma = (V, E)$ and a set of subsets of vertices $S = \{\gamma(t)\}_{t \in \mathcal T}$ (with a given function $\gamma : \mathcal T \to \mathcal P(V)$ where $...
-1
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
1
vote
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. ...
6
votes
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 ...
1
vote
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. ...
2
votes
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 ...
1
vote
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?
4
votes
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 ...
0
votes
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 ...
0
votes
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) ...
1
vote
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 ...
1
vote
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 ...
0
votes
0answers
23 views

Understanding Section 2.2 of Practical Graph Isomorphism II by Brendan D. McKay and Adolfo Piperno

I am trying to understand Section 2.2, "Group actions and isomorphisms" in "Practical Graph Isomorphism II" by Brendan D. McKay and Aldofo Piperno: https://arxiv.org/abs/1301.1493 I quote: "Let $\...
2
votes
0answers
39 views

Graph isomorphism and the automorphism group

A common approach to decide whether two given graphs are isomorphic is to compute the so-called canonical label (alternatively, canonical graph) of each graph and to check whether those match or not. ...
1
vote
1answer
62 views

Is it necessary to perform a cycle check in isomorphism?

While checking Isomorphism between two graphs, is it enough if I just check the degrees of all vertices and if the degrees of all vertices connected to every given vertex are identical in both graphs? ...
0
votes
1answer
48 views

Are the following graphs isomorphic? [closed]

The graphs have different cycle lengths. So can they be considered as not isomorphic?
1
vote
0answers
196 views

Can we argue that two graphs are isomorphic iff their adjacency matrices have the same eigenvalues?

Context: Inspired from the idea that we can show the isomorphism between two graphs by showing that the adjacency matrix of one of the graphs can be obtained by interchanging rows&columns (...
1
vote
2answers
175 views

Non isomorphic graphs with closed eulerian chains

I need to construct 2 graphs that are non isomorphic and have 3 of the following properties. Same number of vertices Same number of edges Both contain a closed eulerian path I was thinking of the ...
1
vote
3answers
271 views

Sufficient condition for graph isomorphism assuming same degree sequence

We assume graph to be simple undirected. In general, having the same degree sequence is not sufficient for two graphs to be isomorphic. A trivial example is a hexagon which is connected and two ...
0
votes
1answer
76 views

Is graph Isomorphism distributive on Cartesian Product of graphs?

We know that $G \mathbin\square H$ = $H \mathbin\square G.$ My question is that if $\mathbin\pi(G) \mathbin \square \mathbin\pi(H)$ same as $G \mathbin\square H$? How do I approach this problem. I ...
2
votes
1answer
195 views

How to proof if these graphs are isomorphic or no? [duplicate]

First graph was given by its adjacency matrix, While the second one was given by its edges coordinates, as the theory says graphs are isomorphic by the number of their nodes (one of the signs), as can ...
1
vote
0answers
19 views

Is relational model isomorphism problem GI-complete?

I think that's true, but does anyone know of any paper on the topic?
2
votes
1answer
182 views

What are some good examples of “almost” isomorphic graphs?

I'm examining isomorphisms of simple finite undirected graphs. In order to test whether or not two graphs are isomorphic, there are a lot of "simple" tests one can do, namely, compare the number of ...
0
votes
2answers
682 views

What are the 9 non-isomorphic rooted trees with 5 vertices?

I'm wondering what the non-isomorphic rooted trees with 5 vertices look like. According to the textbook I'm reading, there are 9 of them but I don't know what they look like or how to draw them or if ...
0
votes
1answer
52 views

Proof of similar vertex characteristics in two isomorphic graphs

Prove the following: If G≅H then G and H have the same maximum degree. If G≅H then G and H have the same number of vertices of maximum degree. If G≅H then there is an isomorphism of induced graphs on ...
2
votes
1answer
183 views

Finding Graph Isomorphisms?

I'm still a bit confused about all the ways to find if two graphs are isomorphic. There's drawing the complement, just brute forcing it by counting vertices & edges and trying to match the two, ...
1
vote
0answers
172 views

Graph Theory | Euler's formula and Graph Isomorphism

Exercise: We are given a simple, connected planar graph with n-vertices, each vertex is of degree 4, and 10 faces. Find all possible n, and all the non isomorphic planar graphs with this property. ...
2
votes
2answers
350 views

Determine whether the graph below is isomorphic to Petersen graph.

At left is a graph, $G$, and at right is the Petersen graph. I think they're isomorphic. I would like to know if I'm correct and how I can start a proof.
3
votes
1answer
41 views

Determining isomorphism for multiple graphs

Question: Determine the pairs of isomorphic graphs. My answer so far: The first three graphs have 8 vertices with 3 degree. The last one has 2 vertices with 4 degree so I automatically eliminated ...
1
vote
1answer
30 views

Can we generalize isomorphism of simple graphs?

Two simple graphs are isomorphic if there is some bijection between the vertex sets and edges are preserved under this mapping. Can this also work for multigraphs? I think that the same definition can ...
0
votes
0answers
38 views

Group associated with graphs

Let $(G,\cdot)$ be a finite group and $a,b \in G$. Defines another groups on $G$ under the binary operation $*_a$ and $*_b$ by $x*_ay = xay$ and $x*_b y = xby$, which are denoted by $(G,*_a), (G,*_b)$...
0
votes
1answer
276 views

Graph theory: Isomorphic and Complement graphs

- Background Information: I am studying discrete mathematics by doing some problems in my textbook. I came across a question that I have a solution for, but I don't understand part of the solution. ...
1
vote
2answers
272 views

Show that both graphs drawn below are isomorphic by giving an isomorphism for them. (Petersen Graph)

The question that I'm trying to answer is: "Show that both graphs drawn below are isomorphic by giving an isomorphism for them. Also known as the Petersen Graphs. I dont quite understand what is ...
1
vote
1answer
104 views

Isomorphism, two graphs

My Question: If two graphs have the same vertice, same degree in each vertice, and the same amount of edges, would an adjacency matrix suffice in showing that they are or are not isomorphic? What I ...
2
votes
2answers
188 views

Show that the following graphs are isomorphic

I have the following problem to resolve: If $X=\{1,2,3,4,5\}$ and $V$ is the set of all the subsets of 2 elements of $X$. If $A$ is the set of pairs of elements of $V$ that are disjoint (as ...