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
14 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 ...
3
votes
1answer
38 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 ...
1
vote
1answer
57 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 ...
2
votes
3answers
125 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 ...
6
votes
3answers
159 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
33 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
14 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
18 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
32 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
15 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
51 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
97 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
112 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
45 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
51 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
21 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
66 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
52 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
38 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
24 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
69 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
25 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
19 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
48 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
41 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
19 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
54 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
43 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
58 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
25 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
18 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
41 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
36 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 ...
3
votes
1answer
29 views

when do we say if two graphs are isomorphic and when do we say they are the same?

A complete graph of 4 vertices can be represented with a square and also with a triangle with a vertex in the middle. I'm confused if I should call the two graphs isomorphic or the same? Also, can ...
0
votes
1answer
24 views

Non isomorphic graph and spectrum of a adjacency matrix

Are two non isomorphic graphs with the same spectrum of adjacency matrix possible?
0
votes
2answers
34 views

Graph isomorphisms on 6 vertices with degree 3

I want to find another graph that has 6 vertices and each has degree $3$ that is not isomorphic to these two graphs below. I know that these two graphs are isomorphic. They will all have the same ...
1
vote
3answers
35 views

Are isomorphic graphs also isospectral?

Two graphs are isomorphic if they just have a different labeling for their vertices i.e. if $A$ and $B$ are their adjacency matrices, then, for some permutation matrix $P$, $PAP^T = B$. Two graphs ...
2
votes
2answers
358 views

What is the difference between automorphism and isomorphism of a graph in graph theory?

Please explain with an example the difference between automorphism and isomorphism of a graph.
0
votes
1answer
32 views

Find diffeomorphism transforming the following areas:

Find diffeomorphism transforming the following: interior of the triangle T with vertices in $(0,0),(0,1),(1,0)$ onto the interior of the circle of radius 1 and centre in $(0,0)$. Obviously i am ...
1
vote
1answer
179 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 ...
12
votes
5answers
1k views

How to show these two graphs are not isomorphic?

In my class they gave me some necessary conditions for two graphs to be isomorphic, these two graphs satisfy all of them but I don't think they're isomorphic: Degree sequences are equal. Same amount ...
1
vote
0answers
45 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 ...
1
vote
1answer
83 views

Finding Automorphisms of Irregular graph through Regular Sub-Graphs.

Objective : To find a set of permutations for a irregular graph which is also a set of automorphism. This finding process uses permutations of 2 regular subgraphs of the given graph. Description and ...
1
vote
1answer
68 views

Number of Automorphisms of a Irregular Graph.

I have been looking for results on number of graph automorphisms of irregular graph(upper and lower bound). I searched , but could not find anything which can be used directly. Say, $G$ is $k$ ...
2
votes
1answer
170 views

Solution of Graph Isomorphism in current literature.

As of 2008, the best algorithm for graph isomorphism (Babai & Luks 1983) has run time $2^{O(\sqrt(n log n))}$ for graphs with n vertices. Does this algorithm gives a yes / no answer or provide ...
1
vote
1answer
27 views

A succinct proof that the given graphs (red $K_n$ drawn cyclically, plus blue $2$-paths between closest vertices) have dihedral automorphism groups?

Take the complete graph $K_n$ ($n \geq 3$), on the red-colored vertex set $\mathbb{Z}_n$, say, and add a blue-colored $2$-path between each pair of vertices $v$, and $v+1$, we get a sequence of graphs ...
1
vote
1answer
85 views

Graph Isomorphism of Complete Graph.

what Is the complexity(computational complexity) of graph isomorphism of 1.Complete graphs($K_n$) and 2.Utility graphs (Complete bipartite graphs ,$K_{n,n}$)? is it in polynomial ? Looks ...
2
votes
1answer
202 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
1answer
70 views

Do cycle graphs determine groups up to isomorphism?

This erroneous version of the wikipedia article for Cycle Graphs stated that the cycle graph of different groups could be the same. The immediate error is that it stated that the cycle graph of ...
0
votes
1answer
31 views

Draw all non-isomorph graphs with 7 knots

in our course we had to draw all non-isomorph graphs with 7 knots without loops. Since this is hard to explain I'll add an Image. The blue written part is accepted by the tutor and the pencil ...