# Questions tagged [graph-isomorphism]

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

475 questions
Filter by
Sorted by
Tagged with
36 views

### If the the adjacency matrix of a graph uniquely determines it up to isomorphism, then why is the isomorphism famous?

I hear about "The Graph Isomorphism Problem", and am a bit confused as to where the issue is. Isn't the adjacency matrix ( up to permutation ) unique for a graph up to isomorphism? Can't the ...
1 vote
42 views

1 vote
39 views

### Number of Graphs in $K_n$

I am unsure on the parts $ii, iii, iv$. For $ii$, I am pretty confident that I pick the $4$ vertices in $nC4$ ways, order them in $4!$ ways, and then divide by $2$ as I have double counted due to (a,b,...
1 vote
40 views

### Trees and $K_{10}$

$(ii)$ Ignoring vertex labels, how many distinct trees are there with $5$ vertices? Draw each such tree, and justify your conclusion that there are no more. $(iii)$ Choose one of the trees that you ...
1 vote
46 views

### Degree Sequence Graph Theory

For each of the following degree sequences, either draw a graph with this degree sequence, or prove that no such graph exists. $(i) (1,2,2,3,4,5)$ $(ii) (1,2,2,3,4,4)$ $(iii) (1,2,2,3,5,5)$ $(i)$ -...
18 views

### Map between surface and graph

Now I'm studying topological graphs and I can't find answer to my question. Consider arbitrary graph embedding to an arbitrary surface. Let us fill up the set of edges of this graph until it becomes ...
123 views

### Unique representation of a graph (graph automorphism) in python

I'm trying to implement a boardgame in python, but I'm having quite a bit of trouble finding a clever way to solve the following graph problem. (Image to help visualize the game and pieces I'm talking ...
497 views

### isomorphic graph : Check whether the following graphs are isomorphic or not. If Isomorphic, then establish the isomorphism between them. [closed]

Check whether the following graphs are isomorphic or not. If Isomorphic, then establish the isomorphism between them.
68 views

### How do we feed a file into listg in Nauty [closed]

I am trying to feed a file into the listg -o1 command in Nauty from the command prompt. The file that I am trying to feed into the listg -o1 command is located inside the nauty folder. I have tried a ...
533 views

### If two graphs have same number of trees of every kind, must they be isomorphic?

Set-up. Let $G$ be a (simple) graph. Given a tree $T$, let us define: $$a_{T}(G) = \text{number of subgraphs of } G \text{ that are isomorphic to } T$$ If $T$ and $T'$ are isomorphic, then of course ...
1 vote
29 views

### Split graphs are GI-complete

According to the Wikipedia article about the graph isomorphism problem, it's claimed that split graphs are GI-complete. Does it mean that any two (simple undirected connected) graphs $G_1, G_2$ can be ...
51 views

### Finding nonisomorphic graphs

This is more of a general question that arises from the following: I was asked to find all nonisomorphic cubic graphs (graphs in which every vertex has degree $3$) with $4$, $6$, and $8$ vertices. ...
79 views

### Proving two graphs are isomorphic assuming no knowledge on paths and degrees

I was requested to show the following graphs are not isomorphic. I started studying graph theory literally half an hour ago, and I'm supposed to be able to show this without any knowledge of degrees ...
78 views

### Is the graph non-isomorphism problem in NP?

On Wikipedia, I've found that graph non-isomorphism is not NP-complete, but there is no information about it being in NP. If that's the case, what is the witness of two graphs being non-isomorphic?
213 views

### How to count polyhedral rotations?

Suppose I have a regular polytope $P$ which I'm representing as a graph $G_P$ with vertices and edges. I can already put this data into a computer program to find a list of symmetries of $P$---they'...
1 vote
61 views

### Understanding graph isomorphism through adjacency matrices

Suppose two graphs have adjacency matrix representations $A_1$ and $A_2$ and we want to see if they are isomorphic (assume all graphs here are not directed, so adjacency matrices are symmetric). It is ...
51 views

### Bracelet isomorphism algorithms

I feel like the problem should have been studied, but I wasn't able to find anything precise. Given two bracelets with $n$ beads and $m$ colors, given that the multiplicity of each color is the same, ...
40 views

### Colored hypercubes isomorphism

I would like to extend the method to verify isomorphism between cubes with colored faces in this answer to $4$-cubes (tesseracts) with colored faces ($2$-faces), allowing rotations and reflections, ...
115 views

### Colored cubes isomorphism

Consider two cubes with an arbitrary coloring of faces from 5 possible colors, where each color could appear $0$ to $6$ times. What could be an efficient algorithm for testing whether the two cubes ...
1 vote
104 views

### Check if graph contains an isomorphic subgraph to cycle C3/of lenght 3

Check with the matrix multiplication method whether the simple graph presented in the form of an adjacency matrix contains an isomorphic subgraph to cycle C3 Having such a graph and such a ...