期刊名称：International Journal of Grid and Distributed Computing
印刷版ISSN：2005-4262
出版年度：2016
卷号：9
期号：5
页码：241-264
DOI：10.14257/ijgdc.2016.9.5.21
出版社：SERSC
摘要：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(n 2 ) 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 u 1 added into MaxQ(G) corresponding to the canonical labeling Cmax(G) of G. Further, it utilizes the Cen(G) to calculate the first node u 1 added into MaxQ(G). The proposed methods can be extended to deal with the directed graphs and weighted graphs.
关键词：Degree partition; Canonical labeling; Partition tree; Regular graphs; Centre ; subgraph; Standard regular sequence
