循环图C(9,2)与路Pn的笛卡儿积的交叉数

C(m,2)表示由圈Cm(v1v2…vmv1)增加边vivi+2(i=1,…,m,i+2 (mod m))所得的循环图.C(m,2)的一点悬挂(两点悬挂)是增加一个顶点x(两个顶点x,y)和边xv(边xv,yv)的图,其中v∈V(C(m,2)).我们证明了9阶循环图C(9,2)与路Rn的笛卡儿积的交叉数是10n;C(2m-1,2)的一点悬挂和两点悬挂的交叉数分别是m,2m.     

关于稳定图的一个注记

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。     

一类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的邻点可区别关联色数.     

广义Peterson图的邻点可区别的全染色

设P_(n,k)是一个简单图,其顶点集和边集分别为:V(P_(n,k))={u_0,u_1,…u_(n-1),v_0,v_1,…v_(n-1)},E(P_(n,k))={u_iu_(i+1),u_iv_i,v_iv_(1+k)},则称P_(n,k)为广义Peterson图,其中n≥5,0相似文献   

太阳图的奇优美性和奇强协调性

设k_1,k_2,…,k_n是非负整数,C_n=v_v_2…v_nv_1是有n个顶点n条边的圈,则称图C_n+{v_1v_(11),v_1v_(12),…,v_1v_1k_1,v_2v_(21),…,v_2k_2,…,v_nv_(n1),…,v_nk_n}为(k_1,k_2,…,k_n)轮环图,简记为C(k_1,k_1,…,k_n).研究了太阳图1C_n的奇优美性及其奇强协调性,得到了太阳图1C_n在n为偶数时的奇优美标号算法和奇强协调标号算法,从而证明了太阳图1C_n在n为偶数时是奇优美图和奇强协调图的结论.     

7阶循环图C(7,2)与Pn的笛卡儿积的交叉数

C(7,2)表示由圈C7(v1v2…V7v1)增加边vivi 2(i=1,2,…,7,i 2(rood 7))所得的循环图.目前没有有关七阶图与路、星和圈的笛卡尔积交叉数的结果,我们证明了7阶循环图C(7,2)与路Pn的笛卡儿积的交叉数是8n.     

RAMSEY NUMBER OF HYPERGRAPH PATHS

Let H =(V, E) be a k-uniform hypergraph. For 1 ≤ s ≤ k-1, an s-path P~(k,s)_n of length n in H is a sequence of distinct vertices v_1, v_2, ···, v_(s+n(k-s)) such that {v_(1+i(k-s)), ···, v_(s+(i+1)(k-s))} is an edge of H for each 0 ≤ i ≤ n-1.In this paper, we prove that R(P~(3 s,s)_n, P~(3 s,s)_3) =(2 n + 1)s + 1 for n ≥ 3.     

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

一、 引言令 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=     

关于正定厄米特矩阵的一个不等式的推广

本文推广了正定厄米特矩阵的一个不等式 ,得到以下结果 :设 A( i) ,B( i) ,… ,C( i) ( i=1 ,2 ,… ,m)都是 n阶正定厄米特矩阵 ,A( i)11,B( i)11,… ,C( i)11为其相应矩阵的 k阶顺序主子阵 ,1≤ k≤ n-1 ,α,β,… ,γ都是正实数 ,且 α+β+… +γ=p≥ 1 ,则有∑mi=1|A( i) |α|A( i)11|α,|B( i) |β|B( i)11|β… |C( i) |γ|C( i)11|γ) <∑mi=1A( i) α∑mi=1A( i)11α.∑mi=1B( i) β∑mi=1B( i)11β…∑mi=1C( i) γ∑mi=1C( i)11γ     

一个六阶3-连通图与路Pn的笛卡尔积的交叉数

C(6,2)表示由圈C6增加边vivi 2(i=1,…,6,i 2(m od6))所得的图,把边vivi 2叫做C(6,2)的弦,B表示C(6,2)除去一条弦所得到的图,我们确定了B与Pn笛卡尔积的交叉数为5n-1.     

新题征展(115)

A 题组新编 1.(陈祥)(1)证明:Cmn=(m+1)(m+2)…(m+i)/(n+1)(n+2)…(n+i)Cm+in+i.     

证明图ρ_n~G(i)∪G等的伴随分解及色等价性

设P_m和C_m分别表示具有m个顶点的路和圈,G是任意的r阶连通图,设m是偶数,把路P_(m-1)的标号为偶数的2~(-1)m个顶点分别与2~(-1)mG每个分支的第i个顶点V_i重迭后的图记为ρ_((m-1)+2~(-1)mr)~G(i),令n=(2m+1)+(m+1)r,把图kρ_n~G(i)的每个分支的一个d(v_i)+1度顶点分别与S_(k+1)的k个1度点重迭后所得到的图记为Y_(kn+1)~(PG),运用图的伴随多项式的性质,首先给出了一类图簇ρ_n~G(i)和Y_(kn+1)~(PG)的伴随多项式.在讨论上述图的伴随多项式的基础上,证明了图ρ_n~G(i)∪G、Y_(kn+1)~(PG)∪(k-1)K_1和Y_(kn+1)~(PG)∪(k-1)K_1∪(k-1)G的伴随多项式的因式分解定理,进而证明了这些图类的补图的色等价性.     

完全图循环分解成2-正则图

Alspach提出如下猜想:"设n是奇数并且每个m1,m2,…,mh都是大于等于3而小于等于n的整数.若∑mi=n(n-1)/2,则Kn可以分解成圈Cm1,Cm2,…,Cmh."用记号C(mn11 mn22…mn88)表示由ni个mi长圈,i=1,2,…8组成的2-正则图.设Γ={G((2mi)ni…(2m8)n8)|i ∈[1,8]}.研究了循环(Kv,Γ)-分解的构造方法及其存在性问题,并且证明了Alspach猜想的一些特殊情况.     

有循环极大子群的素数幂阶群的作用是边传递的图(II)

假定Γ是一个有限的、单的、无向的且无孤立点的图,G是Aut(Γ)的一个子群.如果G在Γ的边集合上传递,则称Γ是G-边传递图.我们完全分类了当G为一个有循环的极大子群的素数幂阶群时的G-边传递图.结果为:设图Γ含有一个阶为pn(p是素数,n≥2)的自同构群,且G有一个极大子群循环,则Γ是G-边传递的,当且仅当Γ同构于下列图之一1)pmK1,pn-1-m,0≤m≤n-1;2)pmK1,pn-m,0≤m≤n;3)pmKp,pn-m-1,0≤m≤n-2;4)pn-mCpm,pm≥3,m＜n;5)2n-2K1,1;6)pn-1-mCpm,pm≥3,m≤n-1;7)2pn-mCpm,pm≥3,m≤n-1;8)2pn-mK1,pm,0≤m≤n;9)pn-mK1,2pm,0≤m≤n;10)pn-mK2,pm,0＜m≤n;11)C(2pn-m,1,pm);12)pkC(2pm-k,1,pn-m),0＜k＜m,0＜m≤n;13)(t-s,2m)C(2m 1/(t-s,2m),1,2n-1-m),其中0≤m≤n-1,2n-2(s-1)≡0(mod 2m),t≡1(mod 2),s(≠)t(mod 2m),1≤s≤2m,1≤t≤2n-1;14)∪p i=1 Ci p n-1,其中Ci p n-1=Ca1a1 [1 (i-1)pn-2]a 1 2[1 (i--1)p n-2]…a 1 (pn-1-1)[1 (i-1)p n-2]≌Cp n-1,i=1,2,…,p;15)∪2 i=1 Ci 2n-1,其中Ci 2n-1=Ca1a 1 [1 (i-1)(2n-2-1)]a1 2[1 (i-1)(2n-2-1)]…a1 (2n-1-1)[1 (i-1)(2n-2-1)]≌C2n-1,i=1,2.     

关于环网的直径

1.引言 环网G(N;s_1,s_2,…,s_r)是正则的有向循环图。其节点集用V={0,1,2,…,N-1}表示。N是自然数。网中,从每个节点i向节点i+s_j(modN)都有一条有向弧(i,i+s_j)(i=0,1,…,N-1;j=1,2,…,r;0相似文献   

一种求实多项式的根的方法

假设给定了n次实系数多项式 j(z)= a_0z~n+a_1z~(n-1)+…+a_(n-1)z+a_n,a_n≠0,(1)求(1)的全部根已有很多种方法,其中一些有效的方法是同时或依次求出(1)的根的模ρ_1~(v_1),ρ_2~(v_2),…,ρ_t~(v_t),这里v_1+v_2+…+v_t=n.然后依次求出相应的本的幅角,从而得出(1)的全部根.关于这一类方法的细节,可见[1,2]以及[1,2]中所引文献.     

常系数非齐线性递推式的解的显式表示

本文给出常系数非齐线性递推式(?)的解的显式表达式 H(m)=sum from i=0 to k-1(sum from j=i to k-1 b_ja_(k-j+i))D_(m-k-i)+sum from i=0 to m-k D_if(m-i)(m≥k)其中D_m=sum x_1+2x_2+…+kx_k=m x_j≥0(i=1,2,…,k)(?)a_1~x1a_2~x2…a_k~xk.     

HOLOMORPHIC VECTOR FIELDS AND CHARACTERISTIC FORMS ON A HERMITIAN MANIFOLD

Let M be a compact Hermtian manifold, dim_cM=m, Ω be the curvature form of the Hermitian connection. F is a U(m)-invariant polynomial of degree k相似文献   

Kotzig有向图的度偶序列

1.引言 设T_n是n阶竞赛图,V={v_1,v_2,…,v_n}是T_n的顶点集合。设扩v∈V,T_n中所有被v占优的顶点个数s(v)是v在T_n中的得分,记s(v_i)=s_i,i=1,2,…,n.将v_1,v_2,…,v_n重新排列,使s_1≤s_2≤…≤s_n,则S=(s_1,s_2,…,s_n)即是T_n的得分向量。 在Bondy与Murty的名著《图论及其应用》一书的末尾处列举了50个图论中未解决的问题,其中第45问题是:刻划所有n-1阶子竞赛图都同构的n阶竞赛图。这个问题是Kotzig 1973年提出的(见[1])。作者、黄国勋与林毓材研究了这个问题。文献     

一类拟轮图的亏格（英文）

设W_n是阶数为n+1的轮图.如果添加一个3-度的点到W_n中,所得图的亏格如何变化?本文通过联树模型得到γ(W_n⊕v_(typ)~1)=0,γ(W_n⊕v_(typ)~2)=1,γ(W_n⊕v_(typ)~3)=1.