earticle

영어

This paper establishes a theoretical framework by defining a set of concepts useful for classifying graphs and computing the canonical labeling Cmax(G) of a given undirected graph G, which including the partition tree PartT(G), maximum partition tree MaxPT(G), centre subgraph Cen(G), standard regular sequence SRQ(G), standard maximum regular sequence SMRQ(G), and so on. The implementations of algorithms 1 to 5 show how to calculate them accordingly. The worst time complexities of algorithms 1, 2, 4, and 5 are O(n2) respectively. The time complexity of Algorithm 3 is O(n). By Theorem 3, all leaf nodes of PartT(G) and MaxPT(G) are the regular subgraphs. By Theorem 4 and 5, there exists only one Cen(G) in G. Regular Partition Theorem 6 shows that there exists just one corresponding PartT(G), SRQ(G), MaxPT(G), and SMRQ(G). One can use Classification Theorem 7 to category graphs. Theorem 8 and 9 establish the link between the Cen(G) and the calculation of the first node u1 added into MaxQ(G) corresponding to the canonical labeling Cmax(G) of G. Further, it utilizes the Cen(G) to calculate the first node u1 added into MaxQ(G). The proposed methods can be extended to deal with the directed graphs and weighted graphs.