# Tag Info

18

Mathon has shown that the conjecture used by Corneil and Gotlieb is false. The first reference states this fact. 1- P. Foggia, C.Sansone, M. Vento, A Performance Comparison of Five Algorithms for Graph Isomorphism, Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition, 2001, pp. 188-199. 2- R. Mathon, Sample graphs for isomorphism ...

4

It turns out that yes, indeed, there are two possible definitions for edge-automorphisms... but it turns out that they almost always coincide so that it seems that people often get away with not making the distinction. First, some notation. For a simple graph $G = (V,E)$ we let $\Gamma_V(G)$ define the group of automorpisms over the set of vertices $V$ ...

4

Q2: a nice example is the graph labeling gadget used to prove that: Theorem: Planar 3-connected colored GI $\leq_T^L$ planar 3-connected GI See Thomas Thierauf, Fabian Wagner: The Isomorphism Problem for Planar 3-Connected Graphs Is in Unambiguous Logspace. Theory Comput. Syst. 47(3): 655-673 (2010) The "labeling gadget" used preserves the 3-connectedness ...

3

Graph isomorphism for bipartite graphs is as hard as graph isomorphism for general undirected graphs. Considering bipartite posets (i.e., seeing bipartite graphs as Hasse diagrams of posets), you may see that counting the automorphisms of bipartite posets is as hard as counting the automorphisms of general undirected graphs.

2

This is perhaps a nearly trivial observation, but I couldn't think of another general property just of the automorphisms that would ensure the limiting distribution is uniform. If the automorphism group of the corresponding weighted directed graph is vertex-transitive, then the limiting distribution must be uniform, since then no vertex can be ...

1

Your problem is equivalent to Graph Isomorphism under polynomial-time reductions, even if you include edge colors. First, GI is equivalent (under polynomial-time Turing reductions) to computing generators of the automorphism group. From those generators it is easy (using standard permutation group machinery) to compute the edge orbits in polynomial time. ...

1

Partial answer, don't understand enough group theory, but two papers appear to give partial results. GI for circulants is polynomial. Edged-colored GI for circulants is GI complete via the simple reduction $G \to G'$. Make a clique from $V(G)$ and color an edge $e \in E(G')$ with $1$ iff $e \in E(G)$ and $0$ otherwise. To recover $G$ from $G'$ just take ...

Only top voted, non community-wiki answers of a minimum length are eligible