# Tagged Questions

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

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
1k views

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:
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 ...
34 views

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