[(n-1)/2]强n竞赛图的得分向量

n-竞赛图T_n称为k强的,如果T_n的任意一个由n+1-k个顶点导出的子竞赛图都是强的。 本文证明了下面的结果。设S=(s_1,s_2,…,s_n)是得分向量,n≥3,则S是隐含(n一1)/2]强n-竞赛图的当且仅当h(S)=[(n_1)/2],其中     

3强竞赛图的得分向量

如果对n阶竞赛图T_n的每个h—1元顶点子集U,删点子图T_n—U都是强的,则称T_n是h强的。如果非降的非负整向量R_n=(r_1,r_2,…,r_n)是某个n阶h强竞赛图的得分向量,则称R_n是隐含h强的;如果所有以R_n为得分向量的n阶竞赛图都是h强的,则称R_n是完全h强的。本文给出了得分向量R_n隐含3强和完全3强的判准。     

球超图最大边数的一个下界

设V={v_1,v_2,…,v_n}是一个有限集,E={e_1,e_2,…e_m}是V的非空子集的一个族,满足则称H=(V,E(是一个超图[1],V的元素称为H的顶点,E的元素称为H的边。n称为H的阶。若E中的元素两两不相同,则H称为是简单的。若V是k维欧氏空间ε_k中的点集,且有m个k维闭球B_1,B_2,…。B_m,使B_i中恰含e_1中的点,即     

关于路长分布的若干问题

1976年,R.J.Faudree和R.H.Schelp在密执安(Michigan)国际图论会议上,提出了关于图的路长分布的十四个问题.笔者曾研究过问题1,本文就问题12所提出的猜想给出一个反例,并构造一类图,由此对问题2、3、4给出部分回答.设G=G(V,E)是一无向简单图,其中V是顶点集,E是边集.如果V中两个顶点u,v在G中存在含有i个顶点的一条路,则称性质p_i(u,v)成立.令S_i(2≤i≤n)是G中有     

一类4-正则平面图的邻点可区别关联色数

所谓图R_n是指具有如下结构的平面图:R_n=(V,E),其中顶点集合V={u_1,u_2,…,u_n}U{v_1,v_2,…,v_n},边集合E={u_iu_(i+1),v_iv_(i+1),u_iv_i,u_iv_(i+1)|i=1,2,…,n},其中u_(n+1)=u_1,v_(n+1)=v_1.通过研究R_n的邻点可区别关联着色,给出了当n=4,n是3或者5的正整数倍时,R_n的邻点可区别关联色数.     

GENERALIZED TWO-PART SPERNER FAMILIES

Let m, n, S_1, S_2, …, S_n, be non-negative integers with 0≤m≤n. Assume μ(S_1, S_2, …, S_n)={(a_1, a_2, …, a_n)|0≤a_i≤S_i for each i} is a poser, Where (a_1, a_2, …, a_n)<(b_1, b_2, …, b_n) if and only if a_i相似文献   

关于蕴含Ar,s—可图序列的注记

设G＝（V（G）,E（G）是n阶简单图,其顶点集V（G）＝{v1,…,vr,vr 1,…,vr s,…,vn},n={d1,…,dr 1,…,dr s,…,dn}是G的度序列,且vi的度为dio称G具有性质Ar,s,如果{v1,…,vr,vr 1,…,vr x}的导出子图是完全二部图Kr,s,且{v1,…,vr}和{vr 1,…,vr s}是Kr,s顶点集的二部划分,序列π={d1,…,dr,dr 1,…,dr s,…,dn}称为是蕴含Ar,s－可图的序列判别准则。     

t-可约二部分竞赛图的得分表偶

设 T_(m,n)是 m×n 二部分竞赛图,(X,T)是 T_(m,n)的顶点集合 V(T_(m,n)的有序分划,其中|X|=m,|Y|=n.设 X={x_1,x_2,…,x_m},Y={y_1,y_2,…,y_n}.顶点x_1,x_2,…,x_m 在 T_(m,n)中的得分依次为 a_1,a_2,…,a_m,a_1≤a_2≤…≤a_m;y_1,y_2,…,y_n 在 T_(m,n)中的得分依次为 b_1,b_2,…,b_n,b_1≤b_2≤…≤b_n.记 A=(a_1,a_2,…,a_m),B=(b_1,b_2,…,b_n).有序向量偶(A,B)称为 T_(m,n)的得分表偶.反之,给定有序非负整向量偶(A,B),其中 A=(a_1,a_2,…,a_m),a_1≤a_2≤…≤a_m,B=(b_1,b_2,…,b_n),b_1≤b_2≤…≤b_n,是否存在 m×n 二部分竞赛图 T_(m,n),使得(A,B)是 T_(m,n)的     

关于稳定图的一个注记

Bondy 和 Chvatal 在[1]中引进了稳定图的概念。图 F 称为稳定的,如果对阶数 n 充分大的任意图 G,能从 d(u) d(v)≥2n-4以及 G uv 含同构于 F 的子图推出 G也含有同构于 F 的子图。他们断言:当 s≥2m 2时,图 C_s~m 是稳定图。这里 C_s~m 是一个图,顶点集为{v_1,v_2,…,v_s},顶点 v_i 的邻集 N(v_i)={v_(i 1),…,v_(i m),v_(i-1),…,v_(i-m)}(下标 mod s),i=1,2,…,s。     

关于哈密顿线图的一个注记

一、 引言令 G 是顶点集合为 V(G)且边集合为 E(G)的简单图.图 G 的线图 L(G)是顶点集合为 E(G)的图,L(G)的两个顶点,e_1和 e_2是相邻接的当且仅当 e_1和 e_2在 G中有一个公共顶点.图 G 的一条通道是点与边的一个交替序列 v_0,e_1,v_1,…,v_(n-1),e_n,v_n 其中 e_i(i=     

(0,1)-矩阵类(?)(R,S)

我们把元素全部是1或0的矩阵称为(0,1)-矩阵。设A是一个m×n阶(0,1)-矩阵,其第ⅰ行全部元素之和为r_i(1≤i≤m),第j列全部元素之和为s_j(1≤j≤n)。那么称向量R=(r_1,r_2,…,r_m)为A的行和向量;S=(s_1,s_2,…,s_n)为A的列和向量。所谓具有行和向量R,列和向量S的(0,1)-矩阵类(R,S)是指:     

五类特殊图的三种距离矩阵的特征多项式

设G是一个具有顶点集V(G)={v_1,v_2,…,u_n}的n阶简单图.设d_(i,j)=d(v_i,v_j)表示图G中任意两个顶点v_i与v_j的距离.矩阵D(G)=[d_(i,j)]_(n×n)定义为图G的距离矩阵.定义Tr(v)=∑_(ueV(G))d(u,u)为图G中顶点u的点传递度.Diag(Tr)表示以G中顶点的点传递度为主对角线上元素的对角矩阵.则矩阵D~L(G)=Diag(Tr)一D(G)和D~Q(G)=Diag(Tr)+D(G)分别定义为图G的距离拉普拉斯矩阵和距离无符号拉普拉斯矩阵.分别得到五类特殊图的距离,距离拉普拉斯,距离无符号拉普拉斯的特征多项式的一般表达式.     

The k-point Exponent Set of Primitive Digraphs with Girth 2

Let D =(V,E)be a primitive digraph.The vertex exponent of D at a vertex v∈V,denoted by exPD(V),is the least integer p such that there is a v→u walk of length p for each u∈V.Following Brualdi and Liu,we order the vertices of D so that exPD(v_1)≤exPD(v_2)≤…≤exPD(v_n).Then exPD(v_k)is called the k- point exponent of D and is denoted by exP_D(k),1≤k≤n.In this paper we define e(n,k):=max{exp_D(k)|D∈PD(n,2)} and E(n,k):= {expD(k)|D∈PD(n,2)},where PD(n,2)is the set of all primitive digraphs of order n with girth 2.We completely determine e(n,k)and E(n,k)for all n,k with n≥3 and 1≤k≤n.     

On Some Classes of Interpolating Splines

In this article, we consider some classes of interpolating spline with difference. derivative and integral interpolating conditions respectively. Let Δ_π:a=x_o相似文献   

关于图的L(2,1)标号核图

图的L(2,1)标号核图来自频率分配问题而导致的图论问题.在本文中,我们证得(i)对任意简单图G,存在G的一个标号核图Gcore,使得L(G)=L(Gcore)和L(G)≥|V(Gcore)|-1;(ii)设图G有p个顶点且边集|E(G)|≠φ,存在路 Pi G(1≤i≤m)和路Hs G(1≤s≤n),其中在G中V(Pi)∩V(Pj)=φ(i≠j),在G中V(P,)∩V(Pt)=φ(s≠t),则有m∑t=1|V(Pt)|+n∑s=1|V(Hs)|-(m+n)≥p;(iii)G是p(p≥5)个顶点的简单图,则有p+3≤L(G)+L(G)≤3p-4.     

k-强竞赛图中外弧泛5顶点的数目

称具有n≥3个顶点的强竞赛图T中的一条弧是泛k的,如果对所有的k≤l≤n来说,它属于每个l-圈.本文证明了每个s-强(s≥4)竞赛图至少包含s+2个顶点使得它们的所有外弧都是泛5的.     

κ-强竞赛图中外弧泛5顶点的数目

称具有n≥3个顶点的强竞赛图T中的一条弧是泛κ的,如果对所有的κ≤l≤n来说,它属于每个l-圈.本文证明了每个s-强(s≥4)竞赛图至少包含s+2个顶点使得它们的所有外弧都是泛5的.     

关于竞赛图弧泛回路性的一类反例

设T(V,A)是p个顶点的竞赛图,若对于任意(v_0,v_1)∈A,在T中存在含有(v_0,v_1)的k-回路C_k(k=3,4,…,p),则竞赛图T称为具有弧泛回路性。若对于任意(v_0,v_1)∈A,在T中存在含有(v_0,v_1)的k-回路C_k(k=3,4,…,p—1),并且至少存在T的一条弧不含于T的任一p-回路中,则竞赛图T称为具有准弧泛回路性。 为了叙述方便引进下列记号: R(p)——p个顶点的正则竞赛图所组成的集合;     

张量空间中高阶导算子的相合数值域

对于A∈C_(n×n),(?)A的k阶导算子δ_m~(k)(A)的相合数值域是指 R(δ_m~(k)(A))={E_k(x)|x∈D_m(A)},1≤k≤m≤n, 其中E_k(x)为C~m上的第k个初等对称函数。 D_m(A)={(diag U~TAU)(?)|U∈(?)_n(C)}。 本文的主要结论是:设A∈C_(n×n),s_1≥…≥s_n为(A+A~T)/2的奇异值,则当1相似文献   

ON SCORE VECTORS AND CONNECTIVITY OF TOURNAMENTS

An n-tournament T is called k-strong (l≤k≤n-2), if every (n+1-k)-subtournament of T is strongly connected. This paper proves that a score vector (s_1, s_2,..., s_n), where s_1≤s_2≤...≤s_n, is the score vector of some k-strong tournament if and only if min{t_1, t_2,..., t_(n-1)}≥k, where t_f=s_1+s_2+...+s_j-j(j-1)/2, j=1, 2,..., n-1.