THE GRAPH ISOMORPHISM-PROBLEM

被引：30

作者：

LIU, X ^{[1
]}

KLEIN, DJ ^{[1
]}

机构：

[1] TEXAS A&M UNIV SYST,DEPT MARINE SCI,GALVESTON,TX 77553

来源：

JOURNAL OF COMPUTATIONAL CHEMISTRY | 1991年 / 12卷 / 10期

关键词：

D O I：

10.1002/jcc.540121012

中图分类号：

O6 [化学];

学科分类号：

0703 ;

摘要：

A chemically and graph-theoretically relevant problem is that of determining whether a pair of graphs G and G' are isomorphic. A two-stage computational test is developed. In the first stage an "eigenvalue-eigenprojector" tabular graph-theoretic invariant is computed, whence if the two tables differ, G and G' must be nonisomorphic. The second, stage, utilizing the tables of the first stage, orders the vertices, thereby leading to a special labeling for them, whence if the associated adjacency matrices for G and G' are equal, it must be that G and G' are isomorphic. The computational implementation, and testing of the algorithm is described.

引用

页码：1243 / 1251

页数：9

共 34 条

[11]

CVETKOVIC D, 1985, LINEAR MULTILINEAR A, V18, P153

[12]

CVETKOVIC D, 1988, SCIENTIA, V1, P41

[13]

CVETKOVIC DM, 1979, SPECTRA GRAPHS, pCH6

[14]

DAMATO SS, 1981, CROAT CHIM ACTA, V54

[15] A TECHNIQUE FOR DETERMINING THE SYMMETRY PROPERTIES OF MOLECULAR GRAPHS [J].

DAVIS, MI ;

ELLZEY, ML .

JOURNAL OF COMPUTATIONAL CHEMISTRY, 1983, 4 (02) :267-275

[16]

Fisher M., 1966, J COMB THEORY, V1, P105, DOI DOI 10.1016/S0021-9800(66)80008-X

[17]

Harary F., 1971, B LOND MATH SOC, V3, P321, DOI [10.1112/blms/3.3.321, DOI 10.1112/BLMS/3.3.321]

[18]

HERNDON WC, 1974, TETRAHEDRON LETT, P671

[19] ISOSPECTRAL GRAPHS AND MOLECULES [J].

HERNDON, WC ;

ELLZEY, ML .

TETRAHEDRON, 1975, 31 (02) :99-107

[20] ON LINE GRAPH OF A SYMMETRIC BALANCED INCOMPLETE BLOCK DESIGN [J].

HOFFMAN, AJ ;

RAYCHAUD.DK .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1965, 116 (04) :238-&

← 1 2 3 4 →