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

Filter by
Sorted by
Tagged with
0
votes
1answer
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$
-1
votes
0answers
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.
1
vote
2answers
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 ...
1
vote
1answer
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 ...
3
votes
2answers
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 ...
1
vote
1answer
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 .
3
votes
2answers
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 ...
2
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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. ...
1
vote
1answer
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 ...
0
votes
0answers
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://...
2
votes
1answer
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 ...
0
votes
1answer
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,...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
72 views

How does naive vertex classification via color refinement induce a ranking on the vertices of a Graph $G$?

Color refinement, also known as naive vertex classification or 1-dimensional Weisfeiler-Lehman algorithm, is a combinatorial algorithm that aims to classify the vertices of an undirected simple graph $...
0
votes
1answer
35 views

edge transitive

Let $G$ be a graph all of whose edge-deleted subgraphs are isomorphic. Is $G$ necessarily edge-transitive? I checked the following link but in the end they conclude without good justification what ...
0
votes
1answer
59 views

Trivalent case of the Graph Isomorphism

I was studying the Luks algorithm and in the chapter for Trivalent Graphs I did not understand on the why the elements $\sigma \in K_{r}$ stabilizes all of the elements of $X_{r}$ and the conclusion ...
0
votes
1answer
34 views

Vertex-transitive, finite case

Let $G$ be a graph all of whose vertex-deleted subgraphs are isomorphic. Show that $G$ is vertex-transitive. I've already seen a proof on this page, but it wasn't complete. Could you please help me?
1
vote
0answers
42 views

Two graphs are isomorphic if there is a bijection between their vertices

"Show that two simple graphs $G$ and $H$ are isomorphic if and only if there is a bijection $\theta:V(G)\to V(H)$ such that $uv\in E(G)$ if and only if $\theta(u)\theta(v)\in E(H)$." If I understand ...
1
vote
2answers
73 views

Graph Theory Isomorphism

Are there any graphs that are isomorphic to its complement? I'm not sure if I can consider just a vertex A with no edges to be the graph and its complement A' to also have no edges which would make ...
0
votes
0answers
22 views

How many undirected 4-vertex graphs are there that are not isomorphic? [duplicate]

I solved this problem by drawing every possible undirected 4-vertex graph and got 11 as an answer. Is there a simpler way to calculate the number of graphs that are not isomorphic?
0
votes
1answer
38 views

Why is there no Isomorphism?

I have a question about he argumentation of this proof. Problem: Given are two graphs $S$ and $T$. All the vertices in graph $S$ have an degree (number of neighbors) of $3$ and the vertices of $T$ ...
5
votes
2answers
222 views

Determine whether the following graphs are isomorphic or not

Determine whether the following graphs are isomorphic or not. $\qquad\qquad(a)\text{ Petersen graph}\qquad\qquad\qquad\qquad\qquad\qquad(b)$ First I check degrees of those two graph and ...
3
votes
1answer
86 views

How to predict all non-isomorphic connected simple graphs are there with $n$ vertices

$(1)\:$How many non-isomorphic connected simple graphs are there with $n$ vertices when n is, $\qquad(a)\:4\qquad(b)\:5$ $(2)\:$Draw all non-isomorphic, cycle free, connected graphs having six ...
1
vote
0answers
41 views

What data structure does Graph Isomorphism Problem assume?

In Haskell, I can easily think of a data structure of quasi-labeled simple graphs: ...
1
vote
1answer
56 views

Finding isomorphic matchings of labelled cliques

There are 2 complete graphs with n vertices each. Assuming that k vertices are coloured 'R' and (n-k) vertices are coloured 'B' for both graphs, how does one find out the number of isomorphic ...
1
vote
1answer
15 views

Subgraph Isomorphism Relaxation

I want to find a more relaxed subgraph isomorphism. Specifically I want to find a subset of vertices in one graph, G, connected by a non-overlapping set of walks, that correspond to another set of ...
0
votes
1answer
22 views

A 3D graph with intersecting edges

Is there any three-dimensional graph, such that at least two edges must always intersect? Here I may have countably many vertices. I feel there should be a similar version of $K_{3,3}$ or $K_5$ for ...
0
votes
0answers
22 views

Classify isomorphism of graph

N and k are positive integers satisfying $ 1<=k < n$ An undirected graph $G_{n,k}= (V_{n,k} ,E_{n,k})$ is defined as follows. $V_{n,k}={1,2,3,...n}$ $E_{n,k}={\{\{u,v\}|u-v \equiv k \, (mod ...
4
votes
2answers
85 views

If all subgraphs of two graphs are pairwise isomorphic, are the graphs themselves isomorphic?

For two graphs $G,H$ let's write $G\cong H$ if they are isomorphic. Let's denote the set of all subgraphs of $G$ by $\mathcal S(G)$. Note that $G\in \mathcal S(G)$ and there can be elements $a,b\in \...
0
votes
1answer
34 views

Prove that if n is of the form of 3k or 3k+1 then $K_n$ can be decomposed in three pairwise isomorphic subgraphs.

The number of edges in Kn is $\frac{n(n-1)}{2}$ so it's clear that either (a) $n$ is a multiple of three or (b) $n-1$ is a multiple of three. The proof doesn't have to be extremely rigorous, I just ...
3
votes
2answers
71 views

Do different graphs exist for these vertex distances?

Good day, I was trying to learn and gain better understanding of the structure of graphs in general. I have a puzzle which tells me only distances between vertices and asks me for the graph which ...
1
vote
1answer
39 views

Split exact sequence

Let $G=\langle a,b:a^8=b^p=1,a^{-1}ba=b^\alpha \rangle$, where $\alpha$ is a primitive root of $\alpha^4 \equiv 1~\text{mod}(4)$, $4$ divides $p-1$. I wants to compute the commutator of $G$. My ...
1
vote
0answers
37 views

isomorphic adjacency matrices to one matrix

I need to generate lots of graphs to train my code. But it didn't have any impact if training graphs are isomorphic. So I need to eliminate isomorphic graphs to save time. For this reason, now I'm ...
1
vote
1answer
27 views

Is the definition of isomorphic an if-and-only-if?

A First Course in Graph Theory by Gary Chartrand and Pink Zhang (2012) defines an isomorphism as so: Two labeled graphs $G$ and $H$ are isomorphic (have the same structure) if there exists a one-...
-1
votes
1answer
78 views

Is composition of isomorphism and complementation of a graph commutative?

Composition of two functions, ${f_1}$ and ${f_2}$, is commutative if ${f_1} \circ {f_2} = {f_2} \circ {f_1}$. Even when the functions are bijective, it is not necessary that their composition is ...
0
votes
0answers
17 views

Graph semiring homomorphism and application

For instance, if $f:G\rightarrow G'$ is a homomorphism from $G$ to a complete graph $G'$ with $ n$ vertices, then the chromatic number of $G=\chi(G')=n$. That is, homomorphism here is being used to ...
1
vote
1answer
39 views

Graph Isomorphism - How to Proceed?

I have the following pair of graphs. [Judith L. Gersting Book] Let $G$ and $H$ be the graphs in the image. For $G$, $1$ and $4$ have degree 3, while for $H$, $c$ and $d$ have degree 3. The rest have ...
3
votes
0answers
71 views

Which of the graphs are isomorphic (GRE math subject test)

Could you guys take a look at the following two screenshots? I believe I, II, and III are all isomorphic to each other, while the answer only gives I and III. For II, consider mapping ABCD to EGFH, ...
2
votes
0answers
208 views

Can all 3 vector products $\left(\sum_i v_i u_i w_i\right)$ define linear subspace modulo permutation of coordinates?

To determine a set of $n$ numbers modulo permutation, we can use permutation invariants e.g. some symmetric polynomials like $(\sum_i(x_i)^k)_{k=1..n}$. The big question is how to generalize it to ...
0
votes
1answer
65 views

How many different non-isomorphic random graphs of the Erdős–Rényi model exist?

The Erdős–Rényi model $G(n,m)$ gives a random graph on n vertecies with m edges. I'm interested in the number of possible graphs, that can be generated that way. If you ignore isomorphism, there are ...
0
votes
1answer
26 views

Caching a very long random walk with low memory for graph isomorphism test

I want to perform graph isomorphism tests for a very long random walk with fixed windows. That is given a target graph, say a triangle, I want to find how many consecutive 3 nodes in the random walk ...
1
vote
0answers
45 views

Reformulation of equivalence of categories using natural isomorphisms

What is the proof of equivalence of these two conditions for dummies? (1) $F:\cal K\to L$ is full, faithful and essentially surjective on objects (2) $\cal K$ and $\cal L$ are equivalent, i.e. the ...
0
votes
1answer
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 ...
0
votes
0answers
71 views

I can not find my mistake in AHU algorithm to detect if two trees are isomorphic

I am using AHU algorithm to detect if two rooted trees are isomorphic or not, and I used this algorithm, I have sent it to my teacher and my teacher put a comment that there is a mistake in this ...
0
votes
1answer
325 views

Can someone explain what is this proof of AHU algorithm for tree isomorphism means?

Theorem: The canonical number of a rooted tree is an isomorphism invariant, i.e., (T1; r1) ≡ (T2; r2) iff their canonical numbers are the same Proof: The proof is by induction on the level number ...

1
2 3 4 5
7