Isomorphism testing for circulant graphs C n ( a , b )
Isomorphism testing for circulant graphs C n ( a , b )
复制标题
循环图 C n ( a , b ) 的同构测试
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Ugo Pietropaoli
中科院分区：
文献类型：
--
作者：
S. Nicoloso;Ugo Pietropaoli
本文主要研究连通有向/无向循环图Cn（a，B）.我们研究了一些拓扑特征，并定义了一个简单的组合模型，这是新的主题。在此模型的基础上，我们得到了两个循环图Cn（a，B）和Cn（a，B）同构的充要条件.该方法是完全初等的，包括比较{1，. . .，ngcd（n，a）gcd（n，B）-1}，以及验证{gcd（n，a），gcd（n，B）}是否= {gcd（n，a），gcd（n，B）}。它还允许在线性时间内构建映射函数。此外，还分析了互同构图类的性质。
In this paper we focus on connected directed/undirected circulant graphs Cn(a, b). We investigate some topological characteristics, and define a simple combinatorial model, which is new for the topic. Building on such a model, we derive a necessary and sufficient condition to test whether two circulant graphs Cn(a, b) and Cn(a , b) are isomorphic or not. The method is entirely elementary and consists of comparing two suitably computed integers in {1, . . . , n gcd(n,a) gcd(n,b) − 1}, and of verifying if {gcd(n, a), gcd(n, b)} = {gcd(n, a), gcd(n, b)}. It also allows for building the mapping function in linear time. In addition, properties of the classes of mutually isomorphic graphs are analyzed.