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

325 questions
Filter by
Sorted by
Tagged with
23 views

### Isomorphic graphs derived from $K_{10,10}$

How many subgraphs of $K_{10,10}$ exist that are isomorphic to the graph $G$ on the picture? I can think of $P(10,10)$ but I don't think that all of these cases are isomorphic with $G$
9 views

### How to prove that shortest path is a graph invariant?

I want to prove that if f is a isomorphism between graph G and graph H, then d(u,v)=d(f(u)f(v)), where u and v are vertices of G and d(u,v) is the shortest path between u and v.
45 views

### Number of distinct digraphs with 3 edges?

I asked a question like this a while ago but I don't think I worded it very well so here is a second attempt. I am trying to find a systematic way of finding all distinct possible ways a digraph can ...
30 views

### Examine whether the graphs are isomorphic

I need to examine whether the graphs are isomorphic. It is clear that they have the same number of vertices, edges and degree sequence of both the graphs is the same I guess. But again I'm not sure if ...
61 views

### Graph isomorphism in polynomial time

I have one question about the algorithm on testing the Trivalent Graph isomorphism in polynomial time. The paper "Isomorphism of graphs of bounded valence can be tested in polynomial time" by Luks was ...
44 views

### If 2 graphs are isomorphic, are they homeomorphic too?

I'm quite confused about the homeomorphism definition. Vice-versa is definitely not true. But what can we say about the statement: If 2 graphs are isomorphic, they are homeomorphic .
79 views

### Finding $|\!\operatorname{Aut}(L(K_4))|$ using Orbit-Stabiliser Theorem

I know that you can find the size of an automorphism group of a simple graph $G$ by using the Orbit-Stabiliser theorem as follows: let $\DeclareMathOperator{Aut}{Aut}A = \Aut(G)$, and $v$ be a vertex ...
48 views

### Isomorphism of a subset of toroidal graphs constructed from periodical Delaunay triangulation

Let's assume a set of finite number of random points embedded in a 2-periodic 2D cell. Constructing Delaunay triangulation from these points gives a graph in a torus geometry where each intial point ...
24 views

### the nonisomorphic subgraphs of K_3 and drawing them

I believe its 6 although I'm unsure. how I thought about it is if I take K_3 and give it three points a, b, c then the only isomorphic graph is trivial. A B and C are vertices in k_3 and - means ...
24 views

### Ear decomposition of connected graph

Let $G$ be a connected but not 2-connected graph. Also, $G$ does not contain even cycles as subgraphs. Show that every block $B_i$ of $G$ is isomorphic to either an odd cycle or $K_2$ using ear ...
40 views

### Let G be a finite graph. Can G have a subgraph H (H is supposed to be different from G) so that G and H are isomorphic? [closed]

Let G be a finite graph. Can G have a subgraph H (H is supposed to be different from G) so that G and H are isomorphic? Stuck on this question. Don't know how to approach this question. Any answer ...
114 views

### What is the study of relations between structures that are preserved by isomorphisms?

I've been learning about graph theory, which has included a discussion of isomorphisms. It occurred to me that for two sets it is possible to have isomorphisms that preserve different structures. ...
133 views

### Metric quantifying non-isomorphism of graphs?

While isomorphisms between graphs are not unique, they have an exactness that I would like to relax to a metric. Instead of considering 'whether' two graphs are isomorphic, I would like to consider ...
29 views

### Weisfeiler-Lehman (WL) graph isomorphism test for Directed Acyclic Grapgs (DAG)

Does Weisfeiler-Lehman (WL) graph isomorphism test has a variant for Directed Acyclic Graph (DAG), or for Directed Graph (Digraph)? You can find a comprehensive doc introducing WL test here: https://...
26 views

### Reference Request: GI Completeness of Directed, Bipartite, Colored Graphs

I have a proof of various gadgets by which I can show that directed, bipartite, vertex colored graphs are graph isomorphism complete. However, I'd rather just cite the result. Can someone give a ...
27 views

### How is Aut(G) = Aut(G¯)? (where G¯ is the complement of G)

For a Graph G, I am trying to understand how the automorphism of G is equivalent to the automorphism of the complement of G. I understand that an automorphism is an isomorphism of G onto itself. This,...
40 views

### Graph Isomorphism Problem and ZKP

the question I need help in explaining is this - Outline how the Graph Isomorphism Problem can be used to construct a zero-knowledge proof. and Justification for why your scenario meets the ...
31 views

### Graph Isomorphism Help

I am currently trying to seek assistance in regards to graph isomorphism. I believe the graphs are indeed isomorphic as they both have 5 vertices, 5 edges and a degree of 2. However, I just want to ...
72 views

85 views

32 views

### When are two unlabelled simple graphs considered equal?

When are two unlabelled simple (not necessarily connected) graphs considered equal? I don't really find a way to formally state this. Additionally, what might be a way to find the number of ...