q树的色性

称为q树的图是递归定义的,最小的q树是q阶完全图K_q,一个n+1阶的q树是在n阶的q树上添上一个新点,并且添上邻接这个点与n阶的q树上任意选取的q个两两相邻的点的边而得到。     

K_(1,3)-free图中的圈

本文说的是简单图。 设G是任一个n阶的图。如果G中有长为n的圈,则G是哈密顿图。如果对每个k,3≤k≤n,G含有长为k的圈,则说G是泛圈图。如果对G的每个顶点v,图G中都有长为k的圈经过顶点v,则说G是点k圈图。如果对每个k,3≤k≤n,G都是点k圈图,则说G是点泛圈图。     

2维de Bruijn-Good图的自同构群

令m,n为正整数,M为任意集合,M上的2维(m,n)阶de Bruijn-Good图是一有向图,它的顶点集合V由M上的所有m×n阵组成,即     

Hamilton图泛圈性的Ore类条件

在本文中,所有的图都是简单图,未定义的术语是常见的。众所周知,一个n阶图G,若对任何点对x,y;xy(?)E(G)总有d(x)+d(y)≥n,则G是Hamilton图(Ore,1960);进一步,G是泛圈图或二部图~K(n/2),n/2(Bondy,1971年)。     

N阶完全图K_N的t边着色

如果N阶完全图K_N的边用t种颜色着色,则K_N称为是t边着色的。图F_i,l≤i≤t的Ramsey数n(F_1,…,F_i)是这样的最小正整数,使得对于任意一个i边着色完全图K_n,都可以在其中找到某个子图F_i,它是用第i种颜色着色的。当F_1=     

n阶弦图精确个数及脊梁弦图个数的估计

(i)给出n阶弦图个数的精确公式,(ii)给出n阶脊梁弦图个数的上下限.此上下限表明本文的估计为渐近最佳.此外,得到了n阶Vassiliev纽结不变量的维数的上限,即对任意n≥3,上限为1/2(n-1)!;对于较大的n,上限为(1/2(n-1)!-(1/2(n-2)!.此上限是基于Chmutov和Duzhin之工作,并对其结果(n-1)!有所改进.对于n=3和n=4,1/2(n-1)!是最佳值.     

支撑树端点数介值定理的一个简单证明

G.Chartrand在第四届国际图论会议(1980)上提出这样一个问题:若一连通图G分別有含m和n个端点的支撑树,m相似文献   

具有给定叶数的有向树、自由树的计数

在Knuth的名著中,曾对二叉树、有序树、有向树、自由树的一些组合性质及其在计算机科学中的应用作了广泛的讨论,给出了n阶(n个结点)所有结构不同的上述各类树的计数式。近年来,王振宇先后给出了n阶各类树的总叶数公式。作为对上述结果更精细的分类,最     

有限维单Lie代数的拟有理自同构

本文所用述语及符号与文献[1]中所用一致。 以下总假定g是一个X_N型的单有限维复Lie代数,n是取定的一个CSA,△′是相应的根系,{a′_1,…,a′_N}是取定的一个素根系,e_i,f_i,h_i(i=1,2,…N)是取定的一组标准生成元.如文献[1]中§8.2所述,对于g的k阶自同构u,引入记号E_i,F_i,H_i(i=0,1,…,l),那么 E_0,…,E_1生成g.令     

图的度和、连通度和控制圈

令Ｇ是一个ｎ阶图.设Ｃ是Ｇ中的一个圈,如果Ｇ-Ｖ(Ｃ)是空图,那么称Ｃ是控制圈.令δ,κ和α分别表示图Ｇ的最小度、连通度和独立数.用σｋ表示Ｇ中任意ｋ个独立点的度和的最小值.Ｂａｕｅｒ等人[1]证明了:设Ｇ是ｎ阶2连通图.若σ3≥ｎ κ,则Ｇ是Ｈａｍｉｌｔｏｎ图.本文证明了:定理　设Ｇ是ｎ阶3连通图.若σ4≥ｎ 2κ,则Ｇ包含一个最长圈Ｃ,使得Ｃ是一个控制圈.界ｎ 2κ是最好可能的.我们能构造一类图,它们满足定理假设,但不是Ｈａｍｉｌｔｏｎ的.根据定理,我们有如下结论:推论1　设Ｇ是ｎ阶3连通图.若σ4≥ｎ 2κ并且δ≥α,则Ｇ是Ｈａｍｉ…     

AG(n,F_q)中的二次超曲面——q是2的幂的情形

在本文中我们总假定F_q是含q个元素的有限域,而q是2的幂。设,并且取a是F_q中不属于N的一个固定元素。 定理1 设q是2的幂,那么在仿射变换下,AG(n,F_q)中的任一个二次超曲面必化为以下诸二次方程之一为方程的二次超     

q元覆盖码的下界

设K_q(n,R)为任意码长n,覆盖半径R的q元码的最少码字数目,q≥3为正整     

AG(n,F_q)中的二次超曲面——q是2的幂的情形

<正> 在本文中我们总假定F_q是含q个元素的有限域,而q是2的幂。设,并且取a是F_q中不属于N的一个固定元素。 定理1 设q是2的幂,那么在仿射变换下,AG(n,F_q)中的任一个二次超曲面必化为以下诸二次方程之一为方程的二次超     

问题征解(6)

试证在平面上任意n个点中必有3个点,其中一个点对另外两个点的张角不大于π/n。截止期:1992年1月13日(以邮戳为凭)。优胜者名额:50名。     

双曲型空间等距嵌入的一个问题

n维实向量空间R~n中取所有满足条件x_1~2+x_2~2+……+x_n~2<1的点作成一个子集B,在B上定义一个距离,使其中任意两点x与y之间的距离(记作xy)由下式规定之:     

Ramsey数r(3,14)和r(3,15)的新下界

Ramsey数r(p,q)是满足下述条件的最小正整数r:对任意的r个顶点的图G(本文中的图均指无向简单图),则G或有P个顶点的团(即完全子图k_p)或有q个顶点的独立集。Ramsey 1930年证明了Ramsey数的存在性,Ramsey理论的研究在近六十年中也取得了许多有意义的结果(参看文献[2]     

矩阵之弱不可约性及谱的包含域

设Γ(A)为n阶矩阵A的方向图,若Γ(A)的每一顶点都属于Γ(A)的某一环路,则称A为弱不可约矩阵,一矩阵是弱不可约的当且仅当存在一n阶置换阵P使     

关于2树的1因子定理

Bineke等人研究了2树的特征。本文给出了一个2树有1因子的充分必要条件。有3个顶点的2树是一个三角形。当n≥3时,有n 1个顶点的2树T是从有n个顶点的2树T′增加一个新的顶点和一个含这个顶点的三角形     

AG(n,F_q)中的二次超曲面——q是奇素数幂的情形

设F_q是含q个元素的有限域,q是一个奇素数的幂,再设AG(n,F_q)是F_q上的n维仿射空间。设有二次方程     

有限酉几何与PBIB设计(Ⅰ)

设q为素数幂,F_q~2为有q~2个元素的有限域。F_q~2上满足T(?)′=I~(n)的n阶方阵T全体对于矩阵的乘法构成一个群,叫做F_q~2上的n级酉群,记作U_n(F_q~2)。用V_n(F_q~2)表示F_q~2上的n维向量空间。当把U_n(F_q~2)看作V_n(F_q~2)上的变