CJTCS Volume 1999 Article 1

On Finding the Number of Graph Automorphisms

Robert Beals (University of Arizona), Richard Chang (University of Maryland Baltimore County), William Gasarch (University of Maryland College Park) and Jacobo Torán (University of Ulm) 10 February 1999

Abstract

In computational complexity theory, a function f is called b(n) -enumerable if there exists a polynomial-time function that can restrict the output of f(x) to one of b(n) possible values. This paper investigates #GA, the function that computes the number of automorphisms of an undirected graph, and GI, the set of pairs of isomorphic graphs. The results in this paper show the following connections between the enumerability of #GA and the computational complexity of GI.

1. #GA is e^(O(sqrt(n log n))) -enumerable}.
2. If #GA is polynomially enumerable, then GI in R.
3. For epsilon < 1/2 , if #GA is n^epsilon -enumerable, then GI in P.

• Preformatted versions of the article
  • DVI (109,668 bytes)
  • PostScript (508,623 bytes)
  • PDF (396,240 bytes)
  • Audio by AsTeR (to appear)
• Source materials for custom formatting
  • LaTeX ( cj99-01.tex , 79,371 bytes)
  • BIBTeX ( cj99-01.bib , 9,854 bytes)
  • Parameter settings for custom formatting ( cjropts.tex , 165 bytes)
  • Self citation in BIBTeX (311 bytes)
• Online discussion
• Instructions for Readers

---

Volume 1998, Article 4 Article 2
Volume 1999 Published articles

Last modified: Wed Feb 24 15:51:38 CST 1999

---