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

487 questions
Filter by
Sorted by
Tagged with
1 vote
21 views

### Find a graph which is strictly balanced but not strongly balanced.

A graph G is called strictly balanced if all proper subgraphs H of G satisfies $$\frac{|E(H)|}{|V(H)|}\ < \frac{|E(G)|}{|V(G)|}$$ A graph G is called strongly balanced if every subgraph H of G ...
51 views

### Graph isomorphism checking/detection for directed acyclic graphs

The graph isomorphism problem is hard for an arbitrary graph, and certain classes of graphs have been proven to be "GI-complete", which as I understand means they can be reformulated in ...
• 2,649
1 vote
37 views

### $2^{\mathcal{O}(k)} \cdot n^{\mathcal{O}(1)}$ algorithm to break graphs $\mathcal{F}$ in $G$ with vertex deletion.

Let $G$ be any graph. Let $\mathcal{F}$ denote a set of graphs. We say that $G$ is $\mathcal{F}$ free if none of its subgraphs is isomorphic to a graph $f \in \mathcal{F}$. The problem is to delete at ...
88 views

### Exercise 1.1.17 from West

Here is exercise 1.1.17 from Introduction to Graph Theory by Douglas B. West 1.1.17. Prove that $K_n$ has three pairwise-isomorphic subgraphs such that each edge of $K_n$ appears in exactly one of ...
• 147
1 vote
48 views

### Graph isomorphism and finding bijection

Let us consider two bangles. On these bangles let us add $8$ pearls on each bangle, the sequence of colors of pearls are same on both bangle. But the sequence of labels on pearls is not same. Now ...
• 217
125 views

### Is every group isomorphic to a set of isomorphisms?

Informally: Every group is representable (up to an isomorhism) as a group of isomorphisms. Formally: For every group $G$ there exists a binary relation $f$ on some set $U$ such that $G$ is isomorphic ...
• 5,103
1 vote
28 views

### How can't they be isomorphic despite the conditions

Imagine that you have 2x conncected graphs and they have the same number of vertrices of each degree and the same number of cycles of each length how does it come up despite these facts that they are ...
• 65
38 views

### Algorithm for induced subforest of a tree

I'm currently working on my Master's thesis and my cause would be helped a lot of there existed an (efficient) algorithm for deciding if a given tree $G$ contains a forest $H$ as an induced subforest. ...
1 vote
32 views

### Stabilizer of a block system

Let $\text{Sym}(U)$ be the symmetric group on a set $U$. Moreover, let $\Gamma$ by a subgroup of $\text{Sym}(U)$. From now on, we assume that $\Gamma$ acts transitively (in the natural way) on $U$. ...
• 489
1 vote
23 views

185 views

### Prove that two simple graphs on 4 vertices are isomorphic if and only if they have the same degree sequence. [closed]

The possible degree sequence of the simple graph with 4 vertices is $(0,0,0,0)$ or $(0,0,1,1)$ or $(1,1,1,1)$ or $(0,1,1,2)$ or $(0,2,2,2)$ or $(1,1,2,2)$. Then I do not understand how to prove the ...
150 views

### How to determine if two graphs are Isomorphic ? Finding a one to one and onto function.

I have these two graphs here: I wish to determine if they are Isomorphic. I know that I need to find a one to one and onto function, however I can't find a way to do it. My questions are: I know ...
• 313
145 views

### Tree Isomorphism Proof

Okay, I am trying to prove or disprove that "if any two trees have the same number of nodes and every node in tree 1 maps to a distinct node on tree 2 such that they have the same degree, they ...
• 128
99 views

### Is there a graph that satisfies the golden ratio polynomial?

Is there a graph $G$ containing a bridge-edge $e$, such that if you delete the edge $e$, the resulting graph $G-e$ is isomorphic to $G\times G$? Such a graph, if it exists, would be a graph analogue ...
• 17.7k
1 vote
230 views

### Isomorphism graph from MIT 6042

Hi I'm taking the course 6042 of MIT of discrete math (mathematic for computer science) and now I am encountering this problem: Determine which among the four graphs pictured in the Figures are ...
• 97
1 vote
28 views

### Check if directed graph G1 is edge-induced subgraph isomorphic to directed graph G2

I would like to find an algorithm that will check whether a given directed graph is edge-induced subgraph isomorphic to another directed graph. From the literature I've reviewed, I've seen the ...
57 views

### Given pair of graph is isomorphic? [closed]

enter image description hereI am stuck on this graph. Not sure how to map this I have research everywhere but can't find satisfying answer. I am asking this question on someone's behalf I do not know ...
115 views

### Difference between tree, rooted tree and plane rooted tree? [closed]

I am trying to solve a set of problems that require me to find all trees/rooted trees/plane rooted trees with 4 vertices (up to isomorphism). I have a general idea of how to find all trees with 4 ...
• 11
240 views

### Non-isomorphic bipartite Graphs with same degree sequence and cycles

I am still trying to understand the graph isomorphism problem for bipartite graphs. I know two bipartite graphs cannot be isomorphic if they do not possess the same degree sequence or not the same ...
• 41
200 views

### Showing that this graph is homogeneous

A graph is homogeneous when every isomorphism between two finite induced subgraphs can be extended to an automorphism of the whole graph. I was reading Diestel's graph theory where he describes the ...
• 831
52 views

### Different version of graph isomorphism between two directed graph

Background We are given two directed graphs that can have cycles in them, let's call them $G_1$ and $G_2$, where we have a restriction function $(\mid)$ that takes $G_1$ and an argument and returns a ...
• 1,119
40 views

### Graph canonization method that facilitates re-canonizing after vertex deletions?

I'm trying to improve a graph algorithm that involves for a given graph to search through a large number of its induced subgraphs, generated by removing individual vertices. To reduce the size of this ...
• 191
104 views

### Graph Automorphism vs Graph Isomorphism

I am not so sure about the difference between an isomorphism and automorphism. Consider the two graphs below: Isomorphic graphs It is my understanding that these two graphs are isomorphic, as we can ...
• 13
189 views

### Definition of Graph Isomorphism

In "Graph Theory" by Reinhard Diestel, the author defines homomorphisms and isomorphisms between graphs as follows: Let $G=(V,E)$ and $G'=(V', E')$ be two graphs. A map $\varphi:V \to V'$ ...
• 1,268
1 vote
73 views

### Is it decidable if two structures are isomorphic?

Suppose that $S$ is a nested set and let $S_E$ be the set of "pure" elements (that is, elements of $S$ that are not sets). For example, if $S=\{a,\{a,b,c\}\}$ the "pure" elements ...
• 405
1 vote
366 views

### Weisfeiler-Lehman variant Isomorphism test counterexample

I am currently working on isomorphism tests between graphs. I came up with a variant of the Wesifeiler-Lehman algorithm and I am looking for a pair of graphs which would trick the test. Such pair of ...
• 175
87 views

### We are given a graph $K_6$. How many pairwise non-isomorphic graphs can we get if we delete 3 edges? [closed]

I am looking for help with the question above. Actually have no idea what the answer is and especially how to prove the answer. Any help is highly appreciated.
• 31