Some further development on the eigensystem approach for graph isomorphism detection. (English) Zbl 1074.05059
Summary: Many science and engineering problems can be represented by a network, a generalization of which is a graph. Examples of the problems that can be represented by a graph include: cyclic sequential circuit, organic molecule structures, mechanical structures, etc. The most fundamental issue with these problems (e.g., designing a molecule structure) is the identification of structure, which further reduces to be the identification of graph. The problem of the identification of graph is called graph isomorphism. The graph isomorphism problem is an NP problem according to the computational complexity theory. Numerous methods and algorithms have been proposed to solve this problem. Elsewhere we presented an approach called the eigensystem approach. This approach is based on a combination of eigenvalue and eigenvector which are further associated with the adjacency matrix. The eigensystem approach has been shown to be very effective but requires that a graph must contain at least one distinct eigenvalue. The adjacency matrix is not shown sufficiently to meet this requirement. In this paper, we propose a new matrix called adjusted adjacency matrix that meets this requirement. We show that the eigensystem approach based on the adjusted adjacency matrix is not only effective but also more efficient than that based on the adjacency matrix.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 70B15 | Kinematics of mechanisms and robots |
References:
| [1] | R.J. Wilson, L.W. Beineke (Eds.), Applications of Graph Theory, Academic Press, New York, 1979.; R.J. Wilson, L.W. Beineke (Eds.), Applications of Graph Theory, Academic Press, New York, 1979. · Zbl 0426.00006 |
| [2] | Randic, M., On the recognition of identical graphs representing molecular topology, J. Chem. Phys., 60, 10, 3920-3928 (1974) |
| [3] | Dobrjanskyi, L.; Freudenstein, F., Some applications of graph theory to the structural analysis of mechanisms, ASME J. Eng. Ind., 89B, 1, 153-158 (1967) |
| [4] | Mruthyubjaya, T. S., A computerized methodology for structural synthesis of kinematic chains: part 1—formulation, Mech. Mach. Theory, 19, 6, 487-495 (1984) |
| [5] | Sohn, W. J.; Freudenstein, F., An application of dual graphs to the automatic generation of the kinematic structures of mechanisms, ASME J. Mech. Transm., Autom. Des., 108, 3, 392-398 (1986) |
| [6] | Mruthyunjaya, T. S.; Raghavan, M. R., Structural analysis of kinematic chains and mechanisms based on matrix representation, ASME J. Mech. Des., 101, 488-494 (1979) |
| [7] | Uicker, J. J.; Raicu, A., A method for the identification and recognition of equivalence of kinematic chains, Mech. Mach. Theory, 10, 375-383 (1975) |
| [8] | Yan, H. S.; Hall, A. S., Linkage characteristic polynomials: definitions, coefficients by inspection, ASME J. Mech. Des., 103, 578-584 (1981) |
| [9] | Mruthyunjava, T. S.; Balasubramanian, H. R., In quest of a reliable and efficient computational test for detection of isomorphism in kinematic chains, Mech. Mach. Theory, 22, 2, 131-139 (1987) |
| [10] | Kanehisa, M., Graph comparison and path computation methods for predicting molecular networks from genome information, (Keynote on the 8th International Conference on Intelligent System for Molecular Biology 1SMB 2000. Keynote on the 8th International Conference on Intelligent System for Molecular Biology 1SMB 2000, San Diego, California, USA (August 2000)) |
| [11] | Ogata, H.; Fujibuchi, W.; Goto, S.; Kanehisa, M., A heuristic graph comparison algorithm and its application to detect functionally related enzyme clusters, Nucleic Acids Res., 28, 20, 4021-4028 (2000) |
| [12] | Read, R. C.; Cornell, D. G., The graph isomorphism disease, J. Graph Theory, 1, 339-363 (1977) · Zbl 0381.05026 |
| [13] | Schöning, U., Graph isomorphism is in the low hierarchy, J. Comput. Syst. Sci., 37, 312-323 (1998) · Zbl 0666.68048 |
| [14] | Bodlaender, H. L., Polynomial algorithms for graph isomorphism and chromatic index on partial \(k\)-trees, J. Algorithm, 11, 631-643 (1990) · Zbl 0716.68042 |
| [15] | Babel, L., Isomorphism of chordal \((6, 3)\) graphs, Computing, 54, 303-316 (1995) · Zbl 0823.05043 |
| [16] | Collatz, L.; Sinogowitz, U., Spektren endlichen Graphen, Abh. Math. Sem. Hamburg, 21, 1, 63-77 (1957) · Zbl 0077.36704 |
| [17] | Harary, F.; King, C.; Mowshowitz, A.; Read, R. C., Cospectral graphs and digraphs, Bull. Lond. Math. Soc., 3, 321-328 (1971) · Zbl 0224.05125 |
| [18] | Shah, Y. J.; Davida, G. I.; McCarthy, M. K., Optimum features and graph isomorphism, IEEE Trans. Syst. Man, Cybern., SCM-4, 313-319 (1974) · Zbl 0306.05133 |
| [19] | Ambekar, A. G.; Agrawal, V. P., Canonical numbering of kinematic chains and isomorphism problem: min code, Mech. Mach. Theory, 22, 5, 453-461 (1987) |
| [20] | Tang, C. S.; Liu, T., The degree code—a new mechanism identifier, ASME J. Mech. Des., 115, 627-630 (1993) |
| [21] | Y.F. Luo, T.L. Yang, W.Q. Cao, Identification on spatial kinematic chains using incident degree and incident degree code, Proceeding of Eighth World Congress on the Theory of Machines and Mechanisms IFToMM’91, Prague, Czechoslovakia, 1991, pp. 999-1002.; Y.F. Luo, T.L. Yang, W.Q. Cao, Identification on spatial kinematic chains using incident degree and incident degree code, Proceeding of Eighth World Congress on the Theory of Machines and Mechanisms IFToMM’91, Prague, Czechoslovakia, 1991, pp. 999-1002. |
| [22] | Zhang, W. J.; Li, Q., On a new approach to mechanism topology identification, ASME J. Mech. Des., 121, 57-64 (1999) |
| [23] | Mckay, B. D., Practical graph isomorphism, Congr. Numer., 30, 45-87 (1981) · Zbl 0521.05061 |
| [24] | Kim, J. T.; Kwak, B. M., An algorithm of topological ordering for unique representation of graphs, ASME J. Mech. Des., 114, 103-108 (1992) |
| [25] | P.R. He, W.J. Zhang, Q. Li, A new method for detection of graph isomorphism based on the quadratic form, ASME J. Mech. Des. 125 (2003) 640-642.; P.R. He, W.J. Zhang, Q. Li, A new method for detection of graph isomorphism based on the quadratic form, ASME J. Mech. Des. 125 (2003) 640-642. |
| [26] | Liu, B.; Lai, H. J., Matrices in Combinatorics and Graph Theory (2000), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 0958.05003 |
| [27] | Minc, H., Nonnegative Matrices (1988), Wiley: Wiley New York · Zbl 0638.15008 |
| [28] | Seneta, E., Non-negative Matrices and Markov Chains (1981), Springer: Springer New York · Zbl 0471.60001 |
| [29] | He, P. R.; Zhang, W. J.; Li, Q., Eigenvalue and eigenvector information of graphs and their validity in detection of graph isomorphism, (Proceedings of ASME Design Engineering Technical Conferences DETC2002/MECH-34247. Proceedings of ASME Design Engineering Technical Conferences DETC2002/MECH-34247, Montreal, Canada (September 2002)) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
