Isomorphism of graphs with bounded eigenvalue multiplicity

ABSTRACT

We investigate the connection between the spectrum of a graph, i.e. the eigenvalues of the adjacency matrix, and the complexity of testing isomorphism. In particular we describe two polynomial time algorithms which test isomorphism of undirected graphs whose eigenvalues have bounded multiplicity. If X and Y are graphs of eigenvalue multiplicity m, then the isomorphism of X and Y can be tested by an O(n4m+c) deterministic and by an O(n2m+c) Las Vegas algorithm, where n is the number of vertices of X and Y.

REFERENCES

• 1: Babai, L., "Monte Carlo algorithms in graph isomorphism testing," preprint, 1979.
• 2: Babai, L., "Isomorphism testing and symmetry of graphs," Combinatorics 79 (M. Deza and I. G. Rosenberg, eds.) Ann. Discr. Math. 8, 1980, 101-109.
• 3: László Babai, Moderately Exponential Bound for Graph Isomorphism, Proceedings of the 1981 International FCT-Conference on Fundamentals of Computation Theory, p.34-50, August 24-28, 1981
• 4: Biggs, Norman, Algebraic Graph Theory, Cambridge University Press, 1974.
• 5: Cvetkovi-&-cacute;, D., M. Doob and H. Sachs, Spectra of Graphs, Theory and Application, Academic Press, 1980.
• 6: Merrick Furst , John E. Hopcroft , Eugene Luks, A Subexponential Algorithm for Trivalent Graph Isomorphism, Cornell University, Ithaca, NY, 1980
• 7: Furst, M., J. Hopcroft and E. M. Luks, "Polynomial time algorithms for permutation groups," Proc. 21st IEEE FOCS Symp., 1980, 36-41.
• 8: I. S. Filotti , Gary L. Miller , John Reif, On determining the genus of a graph in O(v O(g)) steps(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.27-37, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804395]
• 9: I. S. Filotti , Jack N. Mayer, A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.236-243, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804671]
• 10: Christoph M. Hoffmann, Testing isomorphism of cone graphs(Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.244-251, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804672]
• 11: Hoffmann, C., "On the complexity of intersecting permutation groups and its relationship with graph isomorphism," Tech. Rept. 4/80, Dept. of Informatik, University Kiel, West Germany, 1980.
• 12: C. Hoffmann, "An O(n4) Isomorphism Test for Trivalent Graphs," Manuscript.
• 13: Hoffmann, C., Group-Theoretic Algorithms and Graph Isomorphism, to appear in Springer Lecture Notes in Comp. Science, March 1982.
• 14: Hopcroft, J. and R. Tarjan, "A V log V algorithm for isomorphism of triconnected planar graphs," JCSS 7, 1973, 323-331.
• 15: J. E. Hopcroft , J. K. Wong, Linear time algorithm for isomorphism of planar graphs (Preliminary Report), Proceedings of the sixth annual ACM symposium on Theory of computing, p.172-184, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803896]
• 16: Leighton, F. T. and G. L. Miller, "Numerical analysis of Gaussian elimination and eigenspace calculation," in preparation.
• 17: Leighton, F. T. and G. Miller, "Certificates for Graphs with Distinct Eigenvalues," in preparation.
• 18: David Lichtenstein, Isomorphism for graphs embeddable on the projective plane, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.218-224, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804669]
• 19: Luks, E., "Isomorphism of graphs of bounded valence can be tested in polynomial time," Proc. 21st IEEE FOCS Symp., 1980, 42-49.
• 20: Mathon, R., "A note on the graph isomorphism counting problem," Inf. Proc. Letters 8, 1978, 131-132.
• 21: Gary Miller, Isomorphism testing for graphs of bounded genus, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.225-235, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804670]
• 22: Sims, C., Computational Problems in Abstract Algebra, Ed. John Leech, Pergamon Press, 1970, pp. 176-177.