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

0
votes
0answers
49 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 ...
3
votes
1answer
29 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
34 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
21 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
44 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
246 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
30 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
87 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
195 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
64 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. ...
0
votes
0answers
23 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
132 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
54 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
79 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
104 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
159 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
239 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
36 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
15 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
23 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} ...
0
votes
0answers
34 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 ...
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
57 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
1answer
136 views

Bound on the size of Permutation Set for Isomorphism

This is the second edition of the post. $\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 ...
0
votes
0answers
119 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
59 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
76 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
59 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
98 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. ...
1
vote
2answers
72 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
1answer
27 views

Are these graph non-isomorphic?

Graph $A$ Graph $B$ Please are these graph non isomorphic? and what is the main reason?
0
votes
1answer
20 views

Are these non isomorphic graphs?

I have graph $A$: I have graph $B$: Are graph $A$ and $B$ non-isomorphic because? I think yes, because: graph $A$ has $V_{8}$ with degree vertex $4$ and graph $B$ has $V_{8}$ with degree ...
0
votes
2answers
54 views

How to determine quickly if these graphs are isomorphic?

I have a collection of 4 graphs, each with 7 vertices [see figure]. I have to determine if the last 3 of them are isomorphic to the first one. What I have tried so far: looking at the degree list ...
0
votes
0answers
78 views

“List all non-isomorphic trees with exactly 6 vertices”

I've been given a question which asks me to "list all non-isomorphic trees with exactly 6 vertices". Whilst trying to work out how to tell whether a graph is isomorphic (which I still don't ...
0
votes
1answer
23 views

What is an isomorphic graph (geometrical interpretation)?

I've seen definitions stating that "If $G=(V,E)$ and $G'=(V',E')$ , then a mapping $\theta : V \rightarrow V'$ is an isomorphism if, for all $u,v \in V$, $uv \in E$ if and only if $\theta (u) ...
1
vote
1answer
55 views

Counting Graph Isomorphism

I am self studying graph theory and was wondering: is there a simple way to count/compute the number of subgraphs G that are isomorphic to another graph (say, G')? For instance, if G = the complete ...
2
votes
1answer
52 views

How can you show that 2 (adjacency) matrices are isomorphic?

Would you do it by showing that elementary matrix operations can be used to get from one matrix to the other? If not, how would you show that 2 adjacency matrices are isomorphic?
0
votes
2answers
62 views

Determining if Graphs are Isomorphic.

Is it true that two graphs must be Isomorphic if: They have 8 vertices, each with a degree of 3? They are both connected, without cycles, and have 6 edges? So I know that to be Isomorphic, each ...
1
vote
0answers
31 views

Not isomorphic graphs with same spectrum - exists?

I am wondering if there exists two graphs, which are not isomorphic with the condition that both of them have the same spectrum. Two graphs are isomorphic when they may be drawn in the same way. ...
0
votes
1answer
19 views

Isomorphism type for Graphs

Let $G$ be a set of connected graphs with the following properties: i.for all $g \in G$, $g$ has $n+1$ vertices ii. for every natural numbers from $1$ to $n$, there exists a vertex whose degree is ...
1
vote
1answer
58 views

Proof that graphs are not isomorphic

If two graphs are isomorphic, they must have: the same number of vertices the same number of edges the same degrees for corresponding vertices the same number of connected components I know ...
0
votes
1answer
39 views

Proof that isomorphic graphs must have the same number of vertices

An isomorphism of graphs G and H is a bijection between the vertex sets of G and H. So I know that from definition of a bijection number of vertices must be the same, but how to describe it offically ...