1
vote
1answer
30 views

Promises in the hidden subgroup formulation of graph isomorphism problem

In the 3rd slide of the talk, Graph isomorphism, the hidden subgroup problem and identifying quantum states, by Pranab Sen, the promise of the problem is defined as follows. Given: $G$: group, ...
3
votes
1answer
28 views

Confusion about the hidden subgroup formulation of graph isomorphism

I am going through Quantum factoring, discrete logarithms and the hidden subgroup problem by Richard Jozsa. On page 13, the author discussed the hidden subgroup problem (HSP) formulation of the graph ...
0
votes
2answers
51 views

Restriction on Graph Automorphism

This question referes to a definition in Eugene M. Luks paper "Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time" (1981), page 48, available at ...
1
vote
1answer
107 views

Complete graph invariant

Does anybody know whether the multiset of the determinants (possibly together with the order of the submatrix they refer to) of all the principal minors of the (symmetric) adjacency matrix of a graph ...
2
votes
1answer
210 views

Generating non-isomorphic graph by adding two edges to a fixed graph

I am given a graph $G$ a fixed vertex $v \in V(G)$ and sets $S_1,S_2 \subseteq V(G).$ The problem I am currently studying requires to answer the following question Compute all non-isomorphic ...