Normal forms for trivalent graphs and graphs of bounded valence

ABSTRACT

A function f is defined, mapping graphs with n vertices onto graphs with vertex set {1,...,n} . f(X) is isomorphic to X and X is isomorphic to Y iff f(X) &equil; f(Y). For each d, the restriction of f to graphs of valence d is computable in time O(n&tgr;(d)) for a suitable integer &tgr;(d). For d > 3, the proof uses a recent result of L. Babai, P.J. Cameron and P.P. Pálfy on the order of primitive groups with bounded composition factors; for the trivalent case a more elementary proof is presented.

REFERENCES

• 1: L. Babai, Monte Carlo algorithms in graph isomorphism testing, manuscript, 1979
• 2: L. Babai, P.J. Cameron, P.P. Pálfi, On the order of primitive permutation groups with bounded nonabelian composition factors, to appear
• 3: László Babai , D. Yu. Grigoryev , David M. Mount, Isomorphism of graphs with bounded eigenvalue multiplicity, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.310-324, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802206]
• 4: L. Babai, E.M. Luks, Canonical labeling of graphs, this volume
• 5: M. Fürer, W. Schnyder, E. Specker, Canonical labeling for graphs of bounded degree, Abstract Amer. Math. Soc. 4, No. 2 (1983)
• 6: M. Furst, J. Hopcroft, E. Luks, Polynomial-time algorithms for permutation groups, 21st IEEE Symp. on Foundations of Comp. Sci. (1980), 36-41
• 7: Z. Galil, C.M. Hoffmann, E.M. Luks, C.P. Schnorr and A. Weber, An O(n3 log n) deterministic and an O(n3) probabilistic isomorphism test for trivalent graphs, 23rd IEEE Symp. on Foundations of Comp. Sci. (1982)
• 8: C.M. Hoffmann, Group-Theoretic Algorithms and Graph Isomorphism, Lecture Notes in Computer Science 136, Springer, Berlin, Heidelberg, New York, 1982
• 9: F.T. Leighton and G. Miller, Certificates for graphs with distinct eigenvalues, in preparation
• 10: E. Luks, Isomorphism of graphs of bounded valence can be tested in polynomial time, J. comp. Sys. Sci. 25 (1982), 42-65
• 11: G. Miller, Graph isomorphism, general remarks, J. Comp. Sys. Sci. 18 (1979), 128-142
• 12: R.C. Read, D.G. Corneil, The graph isomorphism disease, J. Graph Theory 1 (1977), 339-363
• 13: W. Schnyder, in preparation, 1982
• 14: H. Wielandt, Finite permutation groups, Academic press, New York, 1964

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Normal forms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Theory