论文部分内容阅读
设n,r,k为正整数且3≤r≤n,k≥2。若对每一个t,r≤t≤n,阶为n的图G恰有k个长为t的圈,则称G是一个n阶r-(k)-泛圈图。当r=3时,我们称r-(k)-泛圈图为(k)-泛圈图。若对每一个奇(偶)t,r≤t≤n,阶为n的图G恰有k个长为t的圈,则称G是一个n阶r-(k)-奇(偶)泛圈图。一个n阶图的圈长分布(CLD)指一个n元整数序列(c1,c2,…,cn),其中ci,i=1,2,…,n表示长度为i的圈的个数。给定一个圈长分布(α1,α2,…,αn),刻画图G满足CLD(G)=(c1,c2,…,cn),ci≥ai,i=1,2,…,n和G具有最小可能边数。记这最小可能边数为 g(α1,α2,…,αn)。 本文主要讨论r-(k)-泛圈图及相关圈长分布的极值问题。本文得到了以下结果: 1、给出一类r-(k)-泛圈图的构造,其中k=2μ,μ∈N*。同时,运用类似方法讨论了r-(k)-奇(偶)泛圈图,其中k=2μ,μ∈N*和r-(k)-泛圈图,其中k=3μ1,k=3μ22μ3,μ1,μ2,μ3∈N*。 2、在r-(k)-泛圈图的基础上,构造了一类圈长分布为(0,0,α1,α2,…,αn),αi≥k,i=1,2,…,n,k=2,3,4的图,并给出了g(0,0,…k,)的上下界。 3、探讨了当r=3时r-(3)-泛圈图,即(3)-泛圈图的存在性问题,并给出一些必要条件。