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

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 ...
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 ...
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 ...
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 ...
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 ...
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?
42 views

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