A Note on the Graph Isomorphism counting Problem

By R. Mathon. 1979

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Spectra of Graphs (2011, background): “The graph isomorphism problem (on graphs with n vertices) can be reduced to the problem of finding the size of the automorphism group of a graph (on at most 2n vertices) (Mathon [289]).”
Graph isomorphism is in SPP (2002, background): “It is well-known from the result of Mathon [16] (see e.”
Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs (2007, background): “To briefly summarize current theoretical knowledge, while no polynomial-time algorithm is known in the context of arbitrary graphs, polynomialtime algorithms are known for numerous restricted families of graphs, including [5, 16, 28, 34], and there is considerable theoretical evidence, including [7,”
The NP-Completeness Column: An Ongoing Guide (1982, background): “It is not known whether the ordinary GRAPH AUTOMORPHISM problem ( | R | = 0 ) is as hard as GRAPH ISOMOR-PHISM, although the problem of counting automorphisms is equivalent to that of counting isomorphisms (and both are equivalent to GRAPH ISOMORPHISM itself) [30].”
An optimal lower bound on the number of variables for graph identification (1989, background): “The importance of symmetries for graph isomorphism testing has been pointed out by Babai and by Mathon [34] who showed that the graph isomorphism problem is equivalent to computing the order of automorphism groups of graphs.”
An optimal lower bound on the number of variables for graph identification (1992, background): “The importance of symmetries for graph isomorphism testing has been pointed out by Babai and by Mathon 34] who showed that the graph isomorphism problem is equivalent to computing the order of automorphism groups of graphs.”
Probabilistic models with unknown objects (2006, background): “Indeed, counting the number of automorphisms of an undirected graph is polynomially equivalent to determining whether two graphs are isomorphic [Mathon, 1979], a problem for which no polynomial-time algorithm is known.”