Skip to main content

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
1 vote
1 answer
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 ...
SHAIBAL kARMAKAR's user avatar
2 votes
1 answer
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 ...
John Cataldo's user avatar
  • 2,649
1 vote
1 answer
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 ...
Yavuz Bozkurt's user avatar
2 votes
2 answers
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 ...
Bryan Busby's user avatar
1 vote
0 answers
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 ...
madhurkant's user avatar
5 votes
1 answer
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 ...
porton's user avatar
  • 5,103
1 vote
1 answer
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 ...
jore12z's user avatar
  • 65
0 votes
0 answers
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. ...
Wannes De Maeyer's user avatar
1 vote
1 answer
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$. ...
Kapur's user avatar
  • 489
1 vote
1 answer
23 views

Question on large induced subgraphs of non-isomorphic graphs

Let $G$ and $H$ be non-isomorphic graphs and consider a bijection $f:V(G)\rightarrow V(H)$. Is it necessarily true that there is some vertex $v\in V(G)$ for which the subgraphs induced by $V(G)\...
Emil Sinclair's user avatar
8 votes
3 answers
418 views

If two vertices induce isomorphic subgraphs when they are removed, are they conjugate?

This feels like a very natural question, but I am struggling to find a reference. Consider a simple graph $G$, and say two vertices are conjugate if there exists an automorphism of $G$ that switches ...
Terence C's user avatar
  • 332
3 votes
1 answer
90 views

Join operation and graph isomorphism.

The join of two graphs $G_1$ and $G_2$, denoted by $G_1 \nabla G_2 $, is a graph obtained from $G_1$ and $G_2$ by joining each vertex of $G_1$ to all vertices of $G_2$. We write $G_1\cong G_2$ for ...
licheng's user avatar
  • 2,474
3 votes
1 answer
151 views

Efficient algorithm for graph isomorphism between graphs differing in only one edge

I am looking for an efficient graph isomorphism algorithm for a special case: given a simple undirected graph $G$ check whether the graphs $G\cup e_1$ and $G\cup e_2$ are isomorphic. The edges $e_1$ ...
lanskey's user avatar
  • 1,066
1 vote
2 answers
64 views

Graph Isomorphism Query: Analyzing Two Graphs for Isomorphism and Proving Non-Existence of Vertex Isomorphism

Let us consider these two graphs (on the left and on the right): Are they isomorphic to each other? I think not because, even though they have the same number of nodes, edges, and the same ...
Mark's user avatar
  • 7,880
0 votes
1 answer
109 views

Planar graphs and isomorphism

If I have a planar graph G and another graph H that's been created by crossing two edges of graph – and its very obviously non-planar. Can I use it as an argument to show that they can not be ...
runtotherescue's user avatar
4 votes
1 answer
279 views

Expected graph edit distance between two random graphs

Consider Erdos-Renyi random graphs $G(n,p)$. Let us independently sample two graphs $G_1$ and $G_2$ following $G(n,p)$. What is the expected graph edit distance (GED) between $G_1$ and $G_2$? Since ...
Vezen BU's user avatar
  • 2,150
1 vote
1 answer
50 views

Identifying isomorphisms between graphs

I have three graphs illustrated above and my goal is to identify if they are isomorphic or not. For disprove that they are isomorphic, I could point out properties such as having a cycle of a certain ...
J P's user avatar
  • 893
4 votes
0 answers
109 views

How many connected nonisomorphic graphs of N vertices given certain edge constraints?

Background: I’m helping a colleague with a theoretical problem in ecology, and I haven’t quite the background to solve this myself. However, I can state the problem clearly, I think: Problem statement:...
Todd Lehman's user avatar
0 votes
1 answer
129 views

Are there 2 non isomorphic graphs with the same Laplacian matrix?

I am trying to form a symmetric Laplacian matrix from an ordinary directed graph but would I be able to form an isomorphism? My gut feeling says it is not injective. Are there any theorems on this. I ...
meatball2000's user avatar
0 votes
1 answer
119 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 ...
Mani's user avatar
  • 402
1 vote
1 answer
49 views

Checking graph isomorphism under a special set of restrictions

I am not sure if graph isomorphism is the appropriate term here. I am looking to compare two matrices where both matrices have the following structure: They are square matrices of identical shape ($n ...
pvelayudhan's user avatar
0 votes
1 answer
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 ...
Ahammad Mostafa Hossain's user avatar
0 votes
2 answers
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 ...
user2899944's user avatar
0 votes
0 answers
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 ...
River Uzoma's user avatar
3 votes
1 answer
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 ...
user326210's user avatar
  • 17.7k
1 vote
1 answer
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 ...
DTJ's user avatar
  • 97
1 vote
0 answers
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 ...
Ilknur Mustafa's user avatar
0 votes
1 answer
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 ...
Nazish Younis's user avatar
0 votes
1 answer
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 ...
Dria's user avatar
  • 11
3 votes
1 answer
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 ...
dips_123's user avatar
2 votes
1 answer
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 ...
kleinbottle's user avatar
0 votes
0 answers
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 ...
Node.JS's user avatar
  • 1,119
2 votes
1 answer
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 ...
MarioVX's user avatar
  • 191
0 votes
1 answer
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 ...
Wygert G's user avatar
4 votes
1 answer
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'$ ...
Koda's user avatar
  • 1,268
1 vote
1 answer
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 ...
T. Rex's user avatar
  • 405
1 vote
2 answers
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 ...
SRichoux's user avatar
  • 175
-1 votes
2 answers
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.
Ilya's user avatar
  • 31
2 votes
2 answers
88 views

Regular graph with certain conditions

Problem: Find a graph $G$ that follows these conditions: i) The number of vertices is 25 ii) $G$ and it's complement have the same degree sequence iii) All vertices of $G$ are of the same degree iv) $...
popcorn's user avatar
  • 311
1 vote
1 answer
61 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,...
user avatar
1 vote
1 answer
60 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 ...
user avatar
1 vote
0 answers
169 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)$ -...
user avatar
1 vote
1 answer
198 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 ...
Tue's user avatar
  • 217
-3 votes
1 answer
2k 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.
diljit singh's user avatar
4 votes
0 answers
77 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 ...
Roy Gourgi's user avatar
22 votes
1 answer
584 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 ...
Prism's user avatar
  • 11.3k
1 vote
1 answer
50 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 ...
ABu's user avatar
  • 451
0 votes
0 answers
70 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. ...
Scene's user avatar
  • 1,611
2 votes
1 answer
144 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 ...
lafinur's user avatar
  • 3,468
7 votes
1 answer
218 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'...
user326210's user avatar
  • 17.7k

1
2 3 4 5
10