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$.
Questions tagged [graph-isomorphism]
489 questions
6
votes
2 answers
How to find isomorphism using matrices?
I'm searching for an easy way to give an isomorphism between two graphs since I never see it with my pair eyes and I found the following answer: This one
I tried applying it in a situation where the vertices have the same degree and things got messy…
user481197
4
votes
1 answer
Are the two graphs isomorphic? Give an isomorphism if possible?
Im doing practice problems to study for an exam.
So Let's assign the four degree vertices together e and 6 so e-6. Then e is adjacent to d, b, f, h and 6 is adjacent to 1, 4, 5, 8 so assign d-1, b-4, f-5, h-8 (fine via symmetry). 4 and 1 are both…
user827508
2
votes
0 answers
are all transitive reductions of a graph isomorphic?
Transitive reduction of a graph is not unique. Take this example:
Now if we remove the labels, the two reduced graphs are isomorphic:
are all transitive reductions of a directed graph isomorphic ? (I'm interested in weakly connected digraphs by…
user667527
- 131
1
vote
2 answers
isomorphism of graph
I have a doubt about an example of isomorphism of graphs. I am looking at the notes of group theory by Donald Kreher. (http://www.math.mtu.edu/~kreher/ABOUTME/syllabus/GTN.pdf). Please see page 9 figure1.1 What I don't get it is why this two graphs…
ricci1729
- 89
1
vote
2 answers
Are these two graphs isomorphic?
I have the attached the images of two graphs. I want to know whether two graphs are planar or not. ? I also want to know whether two graphs are planar or not ?
Raju Parashar
- 113
1
vote
1 answer
Are there any two isomorphic graphs even though their incidence matrices are diffrent?
The question is,
"is it true or false? state your reasons.
There are some isomorphic graphs even though their incidence matrices are different."
Is it true? OR false? If it is true, could you show me some examples?
Thank you.
Jay Shin
- 11
1
vote
0 answers
Nauty graph isomorphism weighted edges
I want to use sofeware Nauty version 2.5 to check if edge-weighted graphs are isomorphic to each other. However weighted edge is not supported by Nauty.
Professor McKay mentioned that there's an example in the manual showing how to make an…
Tina Young
- 11
0
votes
1 answer
Given pair of graph is isomorphic?
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 how to ask this question properly or what i…
Nazish Younis
- 1
- 1
0
votes
1 answer
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 isomorphism must exist, i.e., the graphs are…
Alex
- 23
0
votes
1 answer
Determine if the two graphs are isomorphic
Let G be the graph with vertex and edge sets
$$V = \{1, 2, 3, 4\}$$ and $$E = \{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\}\}$$
and H be the graph with vertex and edge sets
$$V = \{a, b, c, d\} $$and
$$E =…
Robo Jumble
- 93
0
votes
1 answer
Are the two graphs isomorphic? Find an isomorphism if true.
So I said that the answer is yes, because the amount of 3-length cycles in each graph match so the two graphs must be isomorphic.
In order to find an isomorphism I did this.
Let's pick vertex a to correspond with vertex 1, so a-1 (fine via…
user827508
0
votes
0 answers
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 requirements for being a zero knowledge
proof.
I do not…
Danielle
- 1
0
votes
1 answer
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 verify besides what I have mentioned is there…
Danielle
- 1
0
votes
0 answers
Partition Lattices and Isomorphism
I was assigned a Homework question that says this
Prove that every non-empty interval in a partition lattice either has an order isomorphism to a partition lattice or an order-isomorphism to a cartesian product of $n$ partition lattices for some $n…
0
votes
1 answer
Graph Isomorphism and Integer Linear Programming
Let me first state the problem first
Let $X$ and $X'$ be two $n$-vertex graphs with adjacency matrices $A$ and $B$ respectively . An $n \times n $ permutation matrix $P$ encodes an isomorphism $\pi$ from $X$ to $X'$ if and only if $P$ is a solution…
user275490