一类代数二部图的研究

摘要

近年来，具有高度对称性和较大围长的图在极图理论、密码学、编码理论、量子计算以及网络通信等不同领域内均具有重要的应用.
　　1995年Lazebnik和Ustimenko在文[2]中首次提出了一类q-正则、边传递且围长较大的代数二部图D(k，q)，自提出以来便受到学者们的广泛青睐.Füredi等人在文[7]中就二部图D(k，q)的围长提出了一个著名的猜想:对于任意奇数k，素数幂q≥4，D(k，q)的围长等于k+5.为了研究此猜想，文[19]给出了二部图中路径的显示表达公式，并且在顶点色差序列为常数时通过计算齐次多项式ρs(w1，w2，…，wm)的值证明了该猜想在(k+5)/2为有限域Fq的特征的幂时的正确性.随后，文[26]在顶点色差序列为等比数列时计算了齐次多项式ρs(w1，w2，…，wm)的值给出该猜想在(k+5)/2为有限域Fq的特征的幂与q-1的因子的乘积时的证明.本文将进一步研究在更一般情形下齐次多项式ρs(w1，W2，…，Wm)的计算问题，此外，我们还针对二部图D(k，q)与其推广图的同构性问题，设计了二部图连通分支搜索算法.
　　为了进一步研究关于二部图D(k，q)围长的猜想，本学位论文首先讨论了顶点色差序列形如1，1，a,b，a2，b2，…时齐次多项式ρs(w1，w2，…，wm)的计算问题.我们先将该计算问题转化为一个单参数的变系数递归式的求解问题.为了在一种特殊情形下对该递推式进行求解，我们得到了一个新的恒等式j∑i=0iΠs=1xs/(xs-1)j-iΠt=11/(1-xt)=1,并利用该恒等式给出了这种情形下齐次多项式ρs(w1，w2，…，wm)的计算公式.
　　文[36]对D(k，q)进行了推广，得到了与二部图D(2i+3，q)顶点数和围长下界估计相同的二部图Γ（Ti，q），但目前尚不明确它们是否同构.针对此问题，我们提出了二部图连通分支搜索算法，计算了部分二部图Γ(Ti，q)的连通分支数，发现很多情形下二部图Γ(Ti，q)与二部图D(2i+3，q)是不同构的.进一步根据计算结果，我们提出猜想:对于正整数i，k以及素数p，当i=2k时，二部图Γ（Ti，p）与二部图D(2i+3，p)不同构.关于该猜想的研究将有利于构造新的具有较大围长的无穷图族.

目录

摘要

第一章 绪论

1．1 图的基本概念

1．2 代数二部图D(k，q)的提出及研究现状

1．3 本文的主要工作

第二章 二部图D(k，q)与齐次多项式风(w1，w2，?，wm)

2．1 二部图D(k，q)的路径和围长

2．2 齐次多项式ρs(w1，w2，?，wm)的计算

2．3 一个恒等式的证明

2．4 一种特殊情形下ρs(w1，w2，?，wm)的进一步计算

第三章 二部图D(k，q)的推广及连通分支的研究

3．2 D(2i+3，q)与r(Ti，q)的同构性

3．3 二部图Γ(Ti，q)连通分支搜索算法的设计及实现

第四章 结束语

参考文献

附录

致谢

声明