丁超

(安庆师范大学数学与计算科学学院,安徽安庆 246133)

距离模式识别图的判定

丁超

(安庆师范大学数学与计算科学学院,安徽安庆 246133)

本文研究了几类图的距离模式识别性.利用构造法,求出了它们的距离模式识别集和距离模式识别数,提出距离模式识别率的概念,推广了距离模式识别数的概念.

距离模式识别集;距离模式识别数;方格图

1 引言

图的距离模式识别集由Acharya在2006年向Germina提出,随后Germina等人对此展开了研究,一些有意思的结论见文献[1–8].图的一个距离模式识别集是图的一个自同构群,图的每个顶点可由它与距离模式识别集的关系所唯一确定.图可能存在距离模式识别集也可能不存在距离模式识别集,存在距离模式识别集的图称为距离模式识别图,否则称为非距离模式识别图.图G的距离模式识别集可能不唯一,阶数最小的距离模式识别集的阶数称为图的距离模式识别数(记为ρ(G)).如何判定图的距离模式识别数是个有意思的问题.本文判定两类非距离模式识图,得到几类图的距离模式识别集和距离模式识别数,最后给出一个计算距离模式识别率的算法.

2 定义和引理

定义2.1[1]设v为图G(V,E)的任意一个顶点,非空集合M⊆V(G),j为非负整数,记,称集合fM(v)={d(u,v):u∈M}为v的M-距离模式.显然,.如果是单射,那么称M为G的距离模式识别集.记n×(dG+1)阶矩阵为G的直径),将中的非零元用1替换得矩阵

定义2.2设G1(V1,E1)和G2(V2,E2)为两个简单图,它们的积图G1×G2定义为

其中v1～v2表示v1与v2在G2中邻接,u1～u2表示u1与u2在G1中邻……