关键词: 图同构, 顶点不变量, 图不变量, 不可区分图, 简并度

Abstract: In order to find graph invariants with higher performance, fifteen kinds of vertex invariants
are defined by weighted accumulation with the help of vertex data in the process of level-order
traversal. Every kind of vertex invariants are able to compose a graph invariant after being sorted.
The vertex degree is divided into the internal degree, the forward degree, and the backward degree
during the traversal, while the internal degree and the backward degree include the number of loops.
Three kinds of vertex invariants are selected based on the refining performance, and then the graph
invariants are generated. The combination of three kinds of graph invariants performs well in
distinguishing a variety of non-isomorphic connected graphs. Not only all the non-isomorphic graphs
with the number of vertexes N≤8 are distinguishable, but also the number of undistinguishable
graphs with N=9 is reduced from 989 of literature [9] down to 40, with the degeneracies of these
graph invariants approaching 2. Random tests shows that these graph invariants have good
performances in differentiation.

Key words: graph isomorphism, vertex invariants, graph invariants, indistinguishable graphs, degeneracy