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
0
votes
1
answer
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 ...
- 349
1
vote
1
answer
42
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 ...
- 13
0
votes
1
answer
81
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 ...
0
votes
2
answers
64
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 ...
- 261
0
votes
0
answers
44
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 ...
- 23
0
votes
0
answers
10
views
mapping tree graph so edges point to next-oldest sibling?
Is there a name for or relevant work on graphs constructed by taking a tree graph as input and changing the edge targets from the parent to the next-oldest sibling (if it exists)? It has come up in ...
- 133
3
votes
1
answer
81
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 ...
- 17k
1
vote
1
answer
87
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 ...
- 83
1
vote
0
answers
23
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 ...
- 111
0
votes
0
answers
31
views
If two graphs and their Galois covers have the same Ihara zeta function, what can we say about the base graphs?
I know that the Ihara zeta function being the same for two graphs does not necessitate an isomorphism between the graphs, but say instead the zeta functions were the same and the zeta functions of ...
- 43
0
votes
1
answer
46
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 ...
0
votes
1
answer
58
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
3
votes
1
answer
81
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 ...
- 31
2
votes
1
answer
140
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 ...
- 779
0
votes
0
answers
41
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,069
2
votes
1
answer
31
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 ...
- 111
0
votes
1
answer
73
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
4
votes
1
answer
156
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,124
1
vote
0
answers
44
views
How to construct a graph H (with the least number of nodes) that has a subgraph that is isomorphic to each graph in a given set?
Given a finite set of target graphs $\{G_1, G_2, ...\}$ (~20 unique graphs), how to find a graph $H$ (with the lowest number of nodes), that has a subgraph that is isomorphic to each target graph in ...
- 11
1
vote
1
answer
63
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
2
answers
163
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 ...
- 75
-1
votes
2
answers
61
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
2
votes
2
answers
75
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) $...
- 67
1
vote
1
answer
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,163
1
vote
1
answer
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,163
1
vote
0
answers
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)$ -...
- 1,163
0
votes
0
answers
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 ...
0
votes
1
answer
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 ...
- 167
-3
votes
1
answer
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.
4
votes
0
answers
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 ...
- 41
22
votes
1
answer
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 ...
- 10.7k
1
vote
1
answer
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 ...
- 441
0
votes
0
answers
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. ...
- 1,424
2
votes
1
answer
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 ...
- 2,910
0
votes
0
answers
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?
- 161
7
votes
1
answer
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'...
- 17k
1
vote
1
answer
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 ...
- 433
4
votes
0
answers
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, ...
- 2,761
0
votes
0
answers
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, ...
- 2,761
3
votes
1
answer
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 ...
- 2,761
1
vote
0
answers
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 ...
- 11
0
votes
0
answers
12
views
Practical general algorithm for subgraph replacement with multiple target?
Assume the following condition:
There is a directed $G=<V,E,f>$ where $f:V\to C$ maps vertex to kind.
There are some graphs $G_i=<V_i, E_i, f>$ and $G'_i=<V'_i, E'_i, f>$ where $1\...
- 309
4
votes
0
answers
146
views
Is a graphs is determined by its and its complement's multiset of spanning trees?
As shown by this post, a graphs is not determined by its multiset of spanning trees.
In fact, the two graphs below have the same multiset of spanning trees, but are non-isomorphic.
Lets call such ...
- 1,751
5
votes
1
answer
131
views
Graph isomorphism and "level degree" sequences
Given a connected undirected graph $G=\{V,E\}$ of order $n$, let's build for each $v_i\in V$ a list corresponding to the number of newly discovered vertices at each level during a BFS traversal. For ...
- 441
0
votes
1
answer
32
views
Finding a graph isomorphism vs. answering whether an isomorphism exists
I was wondering whether the graph isomorphism problem had two facettes, and whether answering them would be different in terms of complexity.
The facettes are as follows:
Determine that at least one ...
- 23
0
votes
0
answers
48
views
How to determine when two circulant graphs are isomorphic
I came across one problem in GTM244 about the circulant graph:
A circulant is a Cayley graph $CG(\mathbb{Z}_n,S)$, where $\mathbb{Z}_n$ is the additive group of integers modulo $n$. Let $p$ be a ...
- 11
2
votes
1
answer
91
views
Graph properties and isomorphism
For a given list of combined graph properties, is there some general strategy of proving that these properties don’t define a graph up to isomorphism?
For example, let’s call $S(G) = (P, D)$ a ...
- 85
0
votes
2
answers
57
views
Can you turn the TSP into a graph isomorphism problem?
Let's say you found a way to solve graph isomorphisms in polynomial time, so far I am aware that you can solve all cases using László Babai's algorithm in quasi-polynomial time.
Are you able to ...
- 1
36
votes
8
answers
3k
views
Do nonconstructive proofs of isomorphism exist?
I'm interested in proofs of claims of the form "Finite objects $A$ and $B$ are isomorphic" which are nonconstructive, in the sense that the proof doesn't exhibit the actual isomorphism at ...
- 15.7k
0
votes
1
answer
37
views
How is the permutation done in this example?
I have confusion in understanding how the permutation is done in this example.
