# Questions tagged [isomorphism-testing]

Algorithmic questions concerning isomorphism testing. A prime example is the graph isomorphism problem, which is to decide if two input graphs are isomorphic. This tag may also be used for isomorphism testing between other objects (such as groups).

49 questions
Filter by
Sorted by
Tagged with
84 views

93 views

70 views

### Number of non-isomorphic block graphs on n nodes

A block in a graph is a maximal connected subgraph that has no cut-vertex. A complete graph having $n$ nodes is denoted by $K_n$. A block graph is a graph in which each block is a complete graph. For ...
68 views

238 views

### Deciding isomorphism between graphs which interpret in the pure set

I am interested in the following decision problem: Given descriptions of two graphs $G,H$ which interpret in the pure set $\mathbb N=(\{0,1,2,\ldots\},=)$, decide whether $G$ and $H$ are isomorphic....
139 views

### Characterization of non-isomorphic graphs but isomorphic total graphs?

Given a graph $G$, the total graph of $G$, denoted $T(G)$, is the graph with vertex set $V(G) \cup E(G)$, where $a$ and $b$ are adjacent in $T(G)$ if and only if they are adjacent or incident in $G$. ...
103 views

Thesis and a paper give conflicting claims about the complexity of graph isomorphism for directed path graphs. Since this means GI is polynomial likely I am missing something or there is something ...
528 views

### Why is graph automorphism sometimes easier than canonical labeling (for current software)?

László Babai recently hinted that graph isomorphism is solved for all practical purposes: It seems, for all practical purposes, the Graph Isomorphism problem is solved; a suite of remarkably ...
1k views

### Reasons for difficulty of Graph Isomorphism and why Johnson graphs are important?

In http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/ it is mentioned: 'In discussing Johnson graphs, Babai said they were a source of “unspeakable ...
85 views

### What is wrong with this isomorphism preserving transformation to a graph of bounded clique width and bounded rank width?

Got an isomorphism preserving transformation to a graph of bounded clique width and rank width. It, a paper and graphclasses.org imply graph isomorphism is in P, so likely something is wrong. Let $G$ ...
261 views

### Repository of graph classes that are tough to test non-isomorphic pairs from isomorphic pairs

(1) Which graph classes are extremely tough to test for graph non-isomorphic pairs from isomorphic pairs? (2) Is there a repository of adjacencies from such classes?
248 views

### Group acting on two different sets, can isomorphisms be computed efficiently?

For the permutation group isomorphism problem, a permutational isomorphism between two permutation groups is sought. A closely related but seemingly easier problem arises, if an isomorphism between ...
286 views

### Edit distance vs. canonical adjacency matrix distance

Let $G$ and $G'$ be two simple random graphs on the same set of nodes. Let $d_{edit}$ be the edit distance between $G$ and $G'$. Let $\mathbf{A}$ and $\mathbf{A'}$ be the adjacency matrices of the ...
508 views

### Algorithm to determine isomorphism of 2 maximal planar graphs

I read on wikipedia that there are efficient algorithms to answer the question whether 2 (maximal) planar graphs F and G are isomorphic. However, after some (IMHO) substantial searching I don't seem ...
226 views

### “Graph Individualization”[ reference request] [closed]

Context: I am studying Weisfeiler Lehman method(WL method) and have clear idea about 1 and 2 dimensional WL method. I was wondering about the individualization process described below- ...
380 views

### Relationship of Weisfeiler-Lehman algorithm to weak isomorphism of coherent algebras

A coherent algebra is a matrix algebra (over $\mathbb{C}$) closed under conjugate transpose and Schur (entrywise) product, and that contains the identity matrix $I$ and all ones matrix $J$. Given ...
412 views

### Partitioning graph for Graph Isomorphism [closed]

Motivation: I am studying the graph isomorphism problem. I am trying to construct a partitioning method to reduce search cases . Construction: $G$ is an $r$ regular graph, $k$ connected (not a ...
160 views

### Is there a polynomial time algorithm for Poly-trees (Oriented trees) isomorphism?

In terms of graph isomorphism complexity classes Trees have a polynomial time algorithm and Directed Acyclic Graphs (DAG's) do not (so far). What about Poly-trees (oriented trees)? These are DAG's ...
209 views

### Isomorphism problem on the class of induced subgraphs of a hypercube

A problem that I am currently studying translates to the problem of deciding whether two induced subgraphs of the hypercube $Q_k$ are isomorphic. Now it feels to me that this class of graphs is "too ...
(Please see a few paragraphs below by what I mean by “colored node graph isomorphism”.) Some basic definitions for completeness: Given two graphs $G_1=(V_1, E_1)$ and $G_2=(V_2, E_2)$ the graph ...