q树的可重构性

对正整数q,称为q树的图是这样归纳定义的:最小阶的q树是q阶完全图K_q一个n+1阶的q树是在任意取定的一个n阶q树之外添加一个新点,并且添加邻接这个点与该n阶q树上任意取定的q个两两相邻     

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年)。     

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

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

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-3树

2-3树是一种很重要的平衡搜索树。文献[1]中叙述了2-3树(也叫3-2树)的定义(在每个内点上存放一个或两个关键字,且分别具有两个或三个儿子点;所有外点在同一层上)。显然,具有N个关键字的2-3树,其高度h在log_3(N 1)≤h≤log_2(N 1)之间。在这种树上的最坏搜索时间是O(h)。文献[1]中还给出了对它的O(h)时间的插入算法。通过该插入算法插入每个随机关键字而生成的2-3树叫动态自由2-3树。文献[2]研究了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)上的变     

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

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

2维de Bruijn-Good图的同态

令m,n是正整数,F_2是由0和1两个元素组成的有限域,F_2上的2维(m,n)阶deBruijn-Good图是一有向图,它的顶点集合V由F_2上的m×n阵组成,即 它的弧集合由下面的2个集合E_1和E_2组成:     

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)!是最佳值.     

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

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

一类竞赛图

Müller和Pelant已经证明,如果T是n阶非传递竞赛图,n≥5,则T的所有n-2阶子竞赛图具有相同的得分序列的充要条件是,T为二重正则的。在本文中,我们确定所有n-1阶子竞赛图具有相同的得分序列     

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

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

Halin图的边面全色数

定义1 将点数至少为4、所有非一度点(内点)度数至少为3的树T嵌入到平面内,再作一圈C_n.连接T的n个一度点(叶点)所成的平面图,称为Halin图;T称为Halin图的特征树;以C_n为边界的面称为Halin图的外面,其他面称为内面;面边界上的点数为奇数时,称该面为奇面,否则为偶面.平面图两面相邻,当且仅当两面至少有一条公共边.定理1 若G是Halin图,则(i)当G的最大度△(G)≥6时,有X_(ef)(G)=△(G);(ii)当△(G)=3时,有4≤X_(ef)(G)≤5,而X_(ef)(G)=5当且仅当外面f_0的边界上存在一条路P,使得P上的任一边均在点数不     

循环群的最小图

设c(n)是n阶循环群,自同构群与c(n)同构且顶点最少的图称为c(n)的最小图。本文要构造c(n)的最小图。当n=3,4,5和p~t(p≥7,p是素数)时,c(n)的最小图已被人们构造出来了。要构造c(n)的最小图,只要构造c(m)的最小图就行了。这里m为:     

关于简单的MCD图边数的下界

简单的MCD图是指有n个顶点、任何两个圈的长度均不相等且有最大可能边数的简单图,文献[1]中对简单的MCD图的边数f(n)的下界得出     

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

本文指出文献[1]定理2证明的错误之处,给出具有给定叶数的植树、自由树的计数公式。 以G_(n,m)、T_(n,m)、t_(n,m)分别表示n阶m叶植树、有向树、自由树的个数,其计数级数分别记为G(x,y)、T(x,y)、t(x,y)。     

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

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

路径图本征值问题定理的证明

前文给出了利用一级化学反应路径图G_r求取相应的本征方程、本征值和本征向量的三个定理,本文将给以数学上的证明。λE—K用Coates图G_c表示时,是每点有圈的n点图,圈的权为λ—k_(ii),若k_(ii)≠0,则     

关于两类图的整和数

本文中的图均指无向简单图,以N,Z分别表示全体自然数及全体整数集合.对子集S(?)Z(N),S上的整和(和)图定义为图G=(S,E),满足条件对u,v∈S,uv∈E当且仅当u v∈s.此时,S称为G的一个整和(和)标号.一个图称为整和(和)图,如果它同构于某一子集S(?)Z(N)上的整和(和)图.容易验证,对一个有m条边的n阶图G,G∪mK_1是一个和图,只需标定G的顶点为2~i,1≤i≤n,同时对v_i,v_j∈E(G),标定对应的孤立点2~i 2~j即可.因此,对每一个图G,存在一个最小的非负整数r,使G∪rK_1为和图,记σ(G)=r,并称为G的和数.图的整和数ξ(G)类似定义,只是标号范围放宽到整数集上.容易看到ξ(G)≤σ(G).     

关于Caritz的一个猜想

设F_q是阶为q的有限域,多项式f(x)∈F_q[x]称为F_q上的置换多项式,如果f(x)是F_q到自身的一一映射。 在有限域上置换多项式的研究中,Carlitz有一著名猜想(见D.R.Hayes,Duke.Math.J.,34(1967),293—305):对于给定的正偶数n,存在正