论文部分内容阅读
设n,r,t为正整数,G是n阶简单连通无向图。若G中长为r+tj+i的圈恰好有pi(0≤1≤ t-1)个,其中r+tj+t-1≤n,j是p0,p1,…,pt-1重复的次数,则称G为r-(p0,p1,…,pt-1)-泛圈图。当t=1,p0=k,r-(p0,…,pt-1)泛圈图是r-(k)-泛圈图。所谓r-(p0,…,pt-1)-奇(偶)泛圈图,是指若G中长为r+tj+i的奇(偶)圈恰好有pi(0≤1≤ t-1)个,其中r+tj+t-1≤n,j是 p0,p1,…,pt-1重复的次数,则称G为r-(p0,p1,…,pt-1)-奇(偶)泛圈图。所谓n阶图的圈长分布指一个n元整数序列(c1,c2,…,cn),其ci(i=1,2,…,n)表示长度为i的圈的个数。我们用g(a1,a2,…,an)表示所有满足ci≥ai(ai为非负整数)的阶数为n的图的最小可能边数。 本文主要讨论圈长的一些极值问题.本文得到了以下结果: 1.构造出r-(p0,p1,…,p7)泛圈图.同时,运用类似方法讨论了r-(p0,p1,…,p7)-奇(偶)泛圈图。此外,在r-(p0,p1,…,p7)-泛圈图的基础上,刻画出了一类圈长分布为(0,0,c3,c4,…cn),ci≥ai,i=3,4,…,n的图,并给出了其 g(0,0,a3,a3,…,an)的上界。 2.主要采用构造法,给出了当3≤n≤19时,对任意t∈{3,…,n},至少有2个长为t的圈的n阶连通简单图的最小边数g(0,0,2,…,2)的值。