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

learn more… | top users | synonyms

1
vote
1answer
22 views

Number of vertices and edges of two isomorphic graphs

I am given the definition of graph isomorphism as follows: Let $G$ be a graph with vertex set $V_G$ and edge set $E_G$, and let $H$ be a graph with vertex set $V_H$ and edge set $E_H$. Then $G$ is ...
0
votes
1answer
45 views

How string isomorphism is used in graph isomorphism?

Graph isomorphism is a special case of string isomorphism problem. In the paper of Graph Isomorphism in Quasipolynomial Time, the relation has been shown. Let, two strings $x,y$ are associated with ...
1
vote
0answers
23 views

For What Families of Subgraphs, the Subgraph Isomorphism Problem Can be Solved in Polynomial Time?

Are there families of subgraphs that are arbitrarily large and are still easy to match in a larger graph ? By a "family" I mean a graph sequence $\mathcal{G}=\{G_1,G_2,\ldots,G_n,\ldots\}$ which is ...
0
votes
1answer
25 views

String isomorphism definition: Is it for any arbitrary group?

Scott Aaronson's blog, I find the description of string isomorphism as- you’re given two strings $x$ and $y$ over some finite alphabet, as well as the generators of a group $G$ of permutations ...
3
votes
3answers
424 views

Isomorphism vs equality of graphs

I have just started studying graph theory and having trouble with understanding the difference b/w isomorphism and equality of two graphs.According what I have studied so far, I am able to conclude ...
1
vote
0answers
23 views

Automorphism groups of partially cycle graphs

I define partially cycle graphs as follows. If we add the same subgraph to $n-k$ vertices of an $n$-vertex cycle graph, where $1\le k < n$, we create a partially cycle graph. Here are a few ...
1
vote
0answers
20 views

Matching vertices between two graphs

I have a situation where I have two graphs that are supposed to represent the same underlying topology but represent the underlying topology at different resolutions. My goal is to match vertices ...
0
votes
1answer
58 views

Non-trivial graph automorphism groups with $D_n$ as subgroup

I understand that the automorphism group of an $n$ cycle graph is the dihedral group $D_n$ of order $2 n$. From the comment of @Christian, I also understand that $S_n$ is the automorphism group of the ...
0
votes
4answers
1k views

What's the difference between the automorphism and isomorphism of graph?

What's the difference between the automorphism and isomorphism of graph? In graph theory, an isomorphism of graphs $G$ and $H$ is a bijection between the vertex sets of $G$ and $H$, $ f \colon ...
1
vote
1answer
48 views

Are there any two isomorphic graphs even though their incidence matrices are diffrent?

The question is, "is it true or false? state your reasons. There are some isomorphic graphs even though their incidence matrices are different." Is it true? OR false? If it is true, could you show ...
0
votes
0answers
20 views

Is there a name for these permutations?

Given adjacency matrix $A$ of a graph is there a name for permutations $P$ such that $A=PAP'$? Is this an automrphic permutation?
2
votes
1answer
42 views

Are two graphs isomorphic if there is a bijective distance-preserving map between them?

Suppose that there exist two connected graphs $G$ and $H$ and a one-to-one function $\varphi$ from the vertex set $V(G)$ onto $V(H)$ such that the distance $\operatorname d_G(u, v) = \operatorname d_H(...
1
vote
2answers
24 views

Isomorphism of two graphs using adjacency matrix

How can I show that the following two graphs are isomorphic: Steps: The given graphs can be written as:
1
vote
1answer
220 views

Bound on the size of Permutation Set for Isomorphism

$\textbf{Claim :}$ $G, H $ are partitioned into sub-graphs $\{ G_1,G_2 \cdots G_x \}$ and $\{ H_1,H_2 \cdots H_x \} $ . For each $G_i$ we constructed a set permutation, $\beta_i$ such ...
2
votes
0answers
34 views

Automorphism and Direct Product of Generating Set

Notation: $H $ are partitioned into sub-graphs $ H_1,H_2 \cdots H_x$ . We see them in the adjacency matrix of $H$ given below- $$H = \begin{bmatrix} H_{(x)} & R_{(x, x-1)} & R_{(x,x-...
1
vote
0answers
23 views

A retract H of G is an induced subgraph of G. show that it is isometric.

Let G and H be graphs. A homomorphism φ : G → H is a map φ : V(G) → V(H) which preserves edges, that is, {x, y} ∈ E(G) ⇒ {φ(x), φ(y)} ∈ E(H). We write G → H if there is a homomorphism φ : G → H. Let ...
2
votes
2answers
102 views

Automorphism group of a graph = Automorphism group of that graph's adjacency matrix?

Is automorphism group (or set) of a graph $G$ equal to the automorphism group (or set) of adjacency matrix of $G$? Example: $G_1, G_2$ are separate graphs where $G_1^{\pi}= G_2$ and $ G= \bar ...
4
votes
1answer
44 views

How to detect automorphism of union of graphs?

On page 1 of Lecture 2, Algebra and Computation , (Course Instructor: V. Arvind), there is a theorem- Theorem 2. With Graph − Iso (graph isomorphism) as an oracle, there is a polynomial time ...
3
votes
0answers
40 views

Isomorphism of Non-Symmetric Matrix when Permutation-Set is given: A simple observation

Context: Consider, two $m \times n$ matrices $A, B$ such that there is a permutation $\kappa$ that such that such that $A^{\kappa}=B$ (Wielandt's notation), i.e. $A, B$ are isomorphic but not ...
0
votes
2answers
27 views

Is it possible to have different solutions for isomorphic graphs?

According to the following graphs below, they are isomorphic. The matching pairs of the isomorphic graphs below are: a - 7 b - 3 c - 5 d - 4 e - 1 f - 2 g - 6 However, I have the following: ...
2
votes
0answers
199 views

Sifting Technique : Construction of Isomorphism from sets of Local Isomorphism(Graph Isomorphism)

Given two graphs $G, H$ (each has $n$ vertices). We, split $G$ into subgraphs $G_1, G_2... G_x$ (total $x$ vertex set). Similarly,assume $H$ has subgraphs $H_1, H_2... H_x$ (total $x$ vertex set). ...
0
votes
1answer
28 views

Properties of non-trivial automorphism

I am reading Sanjeev Arora and Barak Boaz. I am stuck at proving the following which the book assumes to be trivial result. Following are the point I am stuck at If we are given a graph $G$ ( with ...
1
vote
1answer
64 views

How to generate (recursively?) all non-isomorphic trees with 2 types of vertex labels with degree restrictions?

I am not sure if the title makes a whole lot of sense, but what I am trying to do is generate all non-isomorphic trees that obey the following: 1) Each vertex (including leaves) has one of two labels ...
0
votes
0answers
31 views

If graph isomorphism yields a polynomial time algorihtm.

Greeting I'm studying computing theory and are trying to grasp the concept of complexity classes. If graph isomorphism (suspected NPI) turns out to have polynomial time solution. What possible ...
0
votes
0answers
18 views

Vertex-transitivity of the automorphism group of a digraph

I am trying to understand the theorem 3 of Cycles in graphs and groups by Kantor. Theorem $3$ If $G$ is a vertex-transitive group of automorphisms of a digraph $\Gamma$ with outdegree $d \ge 1$, ...
1
vote
0answers
11 views

Conway's theorem on the number of orbits on the set of all ordered cycles in a $d$-valent graph

I am trying to understand Conway's theorem on the number of orbits on the set of all ordered cycles in a $d$-valent graph. I quote it from Cycles in graphs and groups by Kantor. Theorem $1$ (...
7
votes
3answers
291 views

Is there any algorithm to find Isomorphism function between two graphs?

Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic. Formally, two graphs and with graph vertices are said to be isomorphic if there is a ...
3
votes
3answers
249 views

Isomorphic graphs

I was wondering if this solution for finding wheter or not two graphs are isomorphic would work: I claim that two graphs are isomorphic if their degree list coincide. For example let's say that I ...
2
votes
1answer
32 views

Why are these two graphs not isomorphic?

My reasoning was that they were isomorphisms because you could just flip the bottom two nodes and you would have the same graph. They should be eligible to be isomorphisms because they have the same ...
0
votes
1answer
92 views

What is the isomorphic graph of k4? [closed]

What is the isomorphic graph of a k4 graph? Is every complete graph isomorphic to itself? If there are any theorems related to it, it would be highly appreciated to be pointed out here. Thanks.
1
vote
1answer
194 views

Can a method related to “Weisfeiler-Lehman Method” provide better time complexity for Graph Isomorphism than existing result?

Cai-Furer-Immerman showed that the W-L(Weisfeiler-Lehman ) hierarchy cannot distinguish general graphs except at linear dimension. Even besides CFI's result, there is good reason to believe that ...
1
vote
1answer
60 views

Graph Isomorphism Algorithm of Vertex Transistive Graphs and other.

What are the best known Graph-Isomorphism algorithms for below graph classes- 1.vertex-transitive, 2. edge-transitive, 3.arc-transitive (or symmetric) 4.distance-transitive. Provide run-times/...
3
votes
2answers
68 views

Two graphs that are not isomorphic?

They have the same number of vertices and edges. The degree sequences are the same (5,4,4,4,4,4,3). Looking at each vertex of degree i, they have edges to vertices of the same degrees in each graph. I'...
0
votes
0answers
26 views

Isomorphism between a Cartesian plane and its rescaled version

Definition. Let $M$ be a model of Neutral Geometry and $t > 0$ a positive real number. The rescaled model $M_t$ is defined as follows: • The points of $M_t$ are the same as those of $M$; • The ...
1
vote
1answer
86 views

Coloring/Labelling problem in Polynomial reduction of Isomorphism

** Question :** Notice the inequality inside yellow box. If $i_1$ has $n$ possible vertex, then $j$ has maximum $(n-1)$ vertices. For $\mu_{i_1,j}$ , it should be $1\leq j \leq (n-1)$ . but it is ...
2
votes
2answers
58 views

Number of Labels used in reduction of Isomorphism of Labelled Graph to Graph Isomorphism

From "Lecture Notes in Computer Science" by Christoph M. Hoffmann , Assume that both $X$ and $X'$ have $n$ vertices. We plan to code the graph labels as suitable subgraphs which we attach to the ...
2
votes
0answers
197 views

NAUTY algorithm [closed]

NAUTY is a Graph Isomorphism(GI) software developed by Brendan McKay to test isomorphism of Graphs. It provides a practical solution to the Graph Isomorphism problem. It is a program for isomorphism ...
4
votes
1answer
84 views

Colored graph isomorphism reduction to uncolored graph isomorphism

I am trying to find a polynomial time reduction from the colored graph isomorphism to the regular graph isomorphism. Doing a search on this problem, I found this article and it seems like theorem 1 is ...
4
votes
3answers
164 views

How Graph Isomorphism is used to determine Graph Automorphism?

From Lecture 2, Algebra and Computation by V. Arvind, (page2,3), I understood below passage- For our graph $G$, let $Aut(G) = H ≤ S_n$. We shall use Weilandt’s notation where $i^\pi$ denotes ...
2
votes
1answer
109 views

The set of isomorphisms from a right coset of the automorphism group $Aut(X)$ in $S_n$.

From "Lecture Notes in Computer Science" by Christoph M. Hoffmann , on page 22- Theorem 4 Let $X$ and $X'$ be two isomorphic graphs with vertex set $V = \{1 ..... n\}$ , Then the set of ...
0
votes
0answers
17 views

Murnaghan–Nakayama rule for order 2 subgroup of symmetric group

I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al. In section 5, a scenario is presented as follows. Here, $G$ is the disjiont ...
0
votes
0answers
37 views

Characterization of non-isomorphic graphs but isomorphic total graphs?

Given a graph $G$, the total graph of $G$, denoted $T(G)$, is the graph with vertex set $V(G) \cup E(G)$, where $a$ and $b$ are adjacent in $T(G)$ if and only if they are adjacent or incident in $G$. ...
1
vote
0answers
29 views

Automorphism group of planar graphs

I am going through Constructive Approach to Automorphism Groups of Planar Graphs by Klavík et al. It has shown that the automorphism group of a planar graph $G$ is as follows. $$ \text{Aut} \left(G\...
1
vote
2answers
77 views

Grape/GAP algorithm for an isomorphic graph for a permutation

Problem: Given a graph G (as an adjacency matrix or a grape graph object), and a permutation $\pi \in S_n$. Find an isomorphic graph $G'$ as another adjacency matrix, under $\pi$. The concept is ...
0
votes
0answers
35 views

The size of the automorphism group of a graph

I am going through QUANTUM MECHANICAL ALGORITHMS FOR THE NONABELIAN HIDDEN SUBGROUP PROBLEM by Grigni et a. It is said on page 14 that the size of the automorphism group of a graph is either $1$ or $2$...
0
votes
1answer
16 views

What's the complexity class of Sub-Polytrees isomorphism?

In terms of Subgraph isomorphism I believe Directed Acyclic Graphs (DAG's) are in the np-complete complexity class. What about Poly-trees (oriented trees)? These are DAG's where the possible paths ...
2
votes
1answer
267 views

Simple connected plane graph G and its dual graph G*; if G is isomorphic to G*, then G is not bipartite?

Let $G$ be a simple connected plane graph where $v>2$, and $G^*$ is its dual graph. Prove that if $G$ is isomorphic to $G^*$, then $G$ is not bipartite. I know that $G$'s number of faces is ...
0
votes
0answers
58 views

NP algorithm to determine if two graphs are isomorphic

I have the following assignment on my Algorithms Analysis course. Given two undirected graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ with $\operatorname{card} (V_1) < \operatorname{card} (V_2)$ ...
0
votes
0answers
129 views

Counterexample for Algorithm of Isomorphism testing of Non-Symmetric Matrices

Claim: $E, F$ are non-symmetric 0-1 matrices of dimension $m \times n$ where $m>n$. Given $F \neq E$, it takes maximum maximum $O( \frac {m^{log_2(m)}} { 2^{\sum log_2(m)} })$ times to check ...
2
votes
0answers
50 views

Are these graphs nonisomorphic?

I have got graph $G$ and graph $H$. My question is are these graphs isomorphic? I think no, because in graph $G$ vertex $v_{2}$ has four neighbours: $v_{1}$ with degree two $v_{8}$ with degree ...