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
16 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
43 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 ...
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 ...
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:
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: ...
1
vote
1answer
63 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$ (...
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 ...
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.
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). ...
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
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 ...
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 ...
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 ...
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 ...
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 ...
7
votes
3answers
290 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 ...
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$. ...
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 ...
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\...
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 ...
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)$ ...
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 ...
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 ...
4
votes
1answer
60 views

Is distance between two graphs defined somehow?

If the two graphs are isomorphic, then their distance is zero. And this distance increases, if vertices or edges are added or removed to/from one of the graphs. Does this "distance" have a special ...
0
votes
0answers
24 views

On graph isomorphism

Consider two undirected graphs $G_1,G_2$ on $n$ vertices given by adjacencies $A,B\in\{0,1\}^{n\times n}$. We can also consider the adjacenies as biadjacencies of two bipartite graphs $B_1,B_2$. Is ...
2
votes
1answer
81 views

isomorphism of graph definition

In Douglas West's book of graph theory, this is how isomorphism of graphs is defined. Please note that graphs need not be simple. An isomorphism from $G$ to $H$ is a bijection $f$ that maps $V(G)$ ...
5
votes
1answer
61 views

What makes graph automorphisms interesting?

I've completed a short course on graph theory and we never studied graph isomorphisms in depth, but I've seen at least a bit of this covered in most graph theory books I've grabbed, that grabbed my ...
3
votes
1answer
134 views

One to One correspondence between vertices of two graphs?

Is it necessary that in two undirected graphs if we need to prove that vertices have one to one correspondence then graph should have same number of edges? What about same number of degree? Can ...
4
votes
1answer
29 views

What is the meaning of saying “two graph vertices are in correspondence?”

What are the conditions for two graphs to be in correspondence? I know for isomorphic - Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic. ...