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$.
508 questions
1 vote
0 answers
25 views
Test if two regular cospectral graphs are isomorphic
Say I have two regular graphs with the same number of nodes and edges, and they are cospectral. How can I test if they are isomorphic? My guess is check diameter or girth. But will that always work? I ...
- 474
0 votes
0 answers
38 views
Is there a fast algorithm to generate all connected, non-2-isomorphic graphs with a given number of edges?
Is there a fast algorithm to generate all connected, non-2-isomorphic graphs with a given number of edges (e.g. 20 edges)? According to Whitney’s definition, “If there is a 1–1 correspondence between ...
- 167
2 votes
1 answer
180 views
Bondy/Murty Graph Theory Exercise 1.2.4 (Number of isomorphisms and automorphisms)
The following question is from Bondy/Murty Graph Theory: 1.2.4 Determine: a) the number of isomorphisms between the graphs G and H of Figure 1.7, b) the number of automorphisms of each of these ...
- 1,022
-2 votes
2 answers
118 views
Find isomorphism between two graphs [closed]
I got stuck at part (b) of this exercise. Is there maybe something like a trick or a quick method to map the variables since in this case we have the following vertex-degree structure: $G_1: a:2, b:5, ...
- 19
1 vote
1 answer
74 views
How do I represent vertex and edge bijections related to graph isomorphism?
I am preparing an exam on discrete mathematics and I have decided to take a look at the famous book Invitation to Discrete Mathematics by Jiri Matousek & Jaroslav Nesetril. The definition of ...
- 55
1 vote
1 answer
46 views
Resources for enumerating isomorphism classes of unlabeled directed multigraphs
I'm looking for resources or datasets that enumerate all isomorphism classes of unlabeled directed multigraphs (i.e., both vertices and edges are unlabeled) for a given number of edges. I've searched ...
- 143
3 votes
0 answers
104 views
Isomorphism between two cospectral graphs with disctinct/simple eigenvalues
Let $X$ and $Y$ be two cospectral graphs with only eigenvalues of multiplicity $1$ (referred to as simple or distinct). Let $X$ have vertex set $V(X) = \{x_{1}, \dots, x_{n}\}$ and $V(Y) = \{y_{1}, \...
- 1,055
0 votes
0 answers
41 views
Number of Inequivalent Labeled Trees on n Vertices
Fix $n$. How many inequivalent labeled trees are there on $n$ vertices, where two labeled trees are equivalent if the labels which disagree are on vertices which are otherwise indistinguishable? For ...
- 157
3 votes
0 answers
185 views
Is this 'TSP polynomial for simple graphs' known or a variation of a known polynomial/ graph invariant?
The 'traveling salesman problem' (TSP) is a well-known NP-hard problem in combinatorial optimization, theoretical computer science and operations research with multiple variations and related ...
- 2,451
1 vote
1 answer
79 views
Counting Pairwise Non-Isomorphic Spanning Trees
Question : Given the graph $G$, we have computed the number of labelled spanning trees to be $14$, which we verified using Kirchhoff’s Matrix-Tree Theorem. Now, I am trying to determine the number of ...
- 965
2 votes
2 answers
86 views
Let $𝐾_{t}^{–2}$ be the graph obtained from $𝐾_{t}$ by deleting two edges. How many subgraphs of $𝐾_{𝑛}$ are isomorphic to $𝐾_{t}^{–2}$?
This is a progression on the lectures my prof has given, for which I don't fully understand the concept. I don't fully understand this question. As reference, here is how my prof progressed through ...
- 69
0 votes
1 answer
97 views
Questions on isomorphism of graphs
According to the following document : https://en.wikipedia.org/wiki/Graph_labeling, the set of vertices(abstract mathematical object) of a graph and the set of the labels(integers, characters, etc.) ...
- 113
2 votes
1 answer
113 views
Graph isomorphism algorithm
I want to check if the two given graphs are isomorphic or not. the following algorithm which is taught by my teacher in class, given two isomorphic n-vertex graphs G1, G2, determines an isomorphism φ ...
- 1
0 votes
1 answer
150 views
Polynomial time algorithm for 3SAT
I followed from this question. I am following the book, Theory of Computational Complexity, 2nd Edition Ding-Zhu Du, Ker-I Ko. I am copying following text from the ...
- 1
1 vote
1 answer
173 views
there exists a polynomial time algorithm for graph non-isomorphism
I am following the book, Theory of Computational Complexity, 2nd Edition Ding-Zhu Du, Ker-I Ko. I am copying following text from the book, Recently an algorithm was ...
- 1