László Babai
David M. Mount
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.
- 1.Babai, L., "Monte Carlo algorithms in graph isomorphism testing," preprint, 1979.Google Scholar
- 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.Google Scholar
- 3.Babai, L., "Moderately exponential bound for isomorphism," Fundamentals of Computation Theory (Proc. Conf. FCT '81, Szeged; F. G-&-eacute;cseg, ed.) Lect. Notes in Comp. Sci. 117, Springer, 1981, 34-50. Google ScholarDigital Library
- 4.Biggs, Norman, Algebraic Graph Theory, Cambridge University Press, 1974.Google Scholar
- 5.Cvetkovi-&-cacute;, D., M. Doob and H. Sachs, Spectra of Graphs, Theory and Application, Academic Press, 1980.Google Scholar
- 6.Furst, M., J. Hopcroft and E. M. Luks, "A subexponential algorithm for trivalent graph isomorphism," Tech. Rept. 80-426, Comp. Sci. Dept., Cornell Univ., 1980. Google ScholarDigital Library
- 7.Furst, M., J. Hopcroft and E. M. Luks, "Polynomial time algorithms for permutation groups," Proc. 21st IEEE FOCS Symp., 1980, 36-41.Google Scholar
- 8.Filotti, I., G. Miller and J. Reif, "On determining the genus of a graph in O(VO(g)) steps," Proc. 11th ACM STOC Symp., 1979, 27-37 Google ScholarDigital Library
- 9.Filotti, I. and J. Mayer, "A polynomial time algorithm for determining isomorphism of graphs of fixed genus," Proc. 12th ACM STOC Symp., 1980, 236-243. Google ScholarDigital Library
- 10.Hoffmann, C., "Testing isomorphism of cone graphs," Proc. 12th ACM STOC Symp., 1980, 244-251. Google ScholarDigital Library
- 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.Google Scholar
- 12.C. Hoffmann, "An O(n4) Isomorphism Test for Trivalent Graphs," Manuscript.Google Scholar
- 13.Hoffmann, C., Group-Theoretic Algorithms and Graph Isomorphism, to appear in Springer Lecture Notes in Comp. Science, March 1982.Google Scholar
- 14.Hopcroft, J. and R. Tarjan, "A V log V algorithm for isomorphism of triconnected planar graphs," JCSS 7, 1973, 323-331.Google ScholarDigital Library
- 15.Hopcroft, J. and J. Wong, "A linear time algorithm for isomorphism of planar graphs," Proc. 6th ACM STOC Symp., 1974, 172-184. Google ScholarDigital Library
- 16.Leighton, F. T. and G. L. Miller, "Numerical analysis of Gaussian elimination and eigenspace calculation," in preparation.Google Scholar
- 17.Leighton, F. T. and G. Miller, "Certificates for Graphs with Distinct Eigenvalues," in preparation.Google Scholar
- 18.Lichtenstein, D., "Isomorphism for graphs embeddable on the projective plane," Proc. 12th ACM STOC Symp., 1980, 218-224. Google ScholarDigital Library
- 19.Luks, E., "Isomorphism of graphs of bounded valence can be tested in polynomial time," Proc. 21st IEEE FOCS Symp., 1980, 42-49.Google Scholar
- 20.Mathon, R., "A note on the graph isomorphism counting problem," Inf. Proc. Letters 8, 1978, 131-132.Google ScholarCross Ref
- 21.Miller, G., "Isomorphism testing for graphs of bounded genus," Proc. 12th ACM STOC Symp., 1980, 218-224. Google ScholarDigital Library
- 22.Sims, C., Computational Problems in Abstract Algebra, Ed. John Leech, Pergamon Press, 1970, pp. 176-177.Google Scholar
Recommendations
Triangle- and pentagon-free distance-regular graphs with an eigenvalue multiplicity equal to the valency
We classify triangle- and pentagon-free distance-regular graphs with diameter d ≥ 2, valency k, and an eigenvalue multiplicity k. In particular, we prove that such a graph is isomorphic to a cycle, a k-cube, a complete bipartite graph minus a matching, ...
The subgraph isomorphism problem for outerplanar graphs
This paper deals with the subgraph isomorphism problem for outerplanar graphs (SUBOUTISOM). In general, since trees and forests are outerplanar, SUBOUTISOM is NP-complete. We show that SUBOUTISOM remains NP-complete even when the strongest connectivity ...
Subgraph Isomorphism, log-Bounded Fragmentation and Graphs of (Locally) Bounded Treewidth
MFCS '02: Proceedings of the 27th International Symposium on Mathematical Foundations of Computer ScienceThe subgraph isomorphism problem, that of finding a copy of one graph in another, has proved to be intractable except when certain restrictions are placed on the inputs. In this paper, we introduce a new property for graphs (a generalization on bounded ...
Comments