一类积图的局部边路替换图的L(2,1)-标号

图(i=0,1,…,n-1)的一个L(2,1)-标号就是从点集到非负整数集的一个函数,且满足任两个相邻顶点标号差至少为2,以及任两个距离为2的点标号不同.图(i=0,1,…,n-1)的一个(2,1)-全标号就是从点集和边集到非负整数集的一个函数且使得:任两个相邻顶点标号差至少为2;任两个相邻边标号标号差也至少为2;以及任两个关联的点和边标号也不同.本文研究路路的积图的局部边路替换图的L(2,1)-标号,基本得到了路路的Cartesian积的局部边路替换图的L(2,1)-标号数.     

关于图的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.     

两类特殊图的L(2,1)-标号

正1引言本文所指定的图均为无向简单图,文中未说明的符号和术语同文献[1].设G=(V,E)是一个图,其顶点集V=V(G)和边集E=E(G).对任意u∈V(G),则N_G(u)为u点在G中的邻域,N_G[u]=N_G(u)∪{u}为u点在G中的闭邻域,d_G(u)=|N_G(v)|为u点在G中的度,而δ=δ(G)和△=△(G)分别为图G的最小度和最大度.在不致混淆情况下,可将N_G(v),N_G[v],△(G),δ(G)分别简单记为N(v),N[v],△,δ.图G中两个顶     

双圈连通图的L(2,1)-labelling

给定图G,G的一个L(2,1)-labelling是指一个映射f:V(G)→{0,1,2,…},满足:当dG(u,v)=1时,f(u)-f(v)≥2;当dG(u,v)=2时,f(u)-f(v)≥1.如果G的一个L(2,1)-labelling的像集合中没有元素超过k,则称之为一个k-L(2,1)-labelling.G的L(2,1)-labelling数记作l(G),是指使得G存在k-L(2,1)-labelling的最小整数k.如果G的一个L(2,1)-labelling中的像元素是连续的,则称之为一个no-holeL(2,1)-labelling.本文证明了对每个双圈连通图G,l(G)=△ 1或△ 2.这个工作推广了[1]中的一个结果.此外,我们还给出了双圈连通图的no-hole L(2,1)-labelling的存在性.     

图的循环带宽和

Abstract. Let G be a simple graph. The cyclic bandwidth sum problem is to determine a labeling of graph G in a cycle such that the total length of edges is as small as possible. In this paper, some upper and lower bounds on cyclic bandwidth sum of graphs are studied.     

关于几类图的L(2,1)标号问题

图G的L( 2 ,1 )标号是一个从顶点集V(G)到非负整数集的函数f(x) ,使得若d(x ,y) =1 ,则｜f(x) -f(y) ｜≥ 2 ;若d(x ,y) =2 ,则｜f(x) -f(y) ｜≥ 1 .图G的L( 2 ,1 ) 标号数λ(G)是使得G有max{f(v) ∶v∈V(G) }=k的L( 2 ,1 )标号中的最小数k .Griggs和Yeh猜想对最大度为Δ的一般图G ,有λ(G) ≤Δ2 .本文给出了Kneser图 ,Mycieklski图 ,Descartes图 ,Halin图的λ值的上界 ,并证明了上述猜想对以上几类图成立     

一类含三角形图的伴随多项式的根

We denote h(G,x) as the adjoint polynomial of graph G. In [5], Ma obtained the interpolation properties of the roots of adjoint polynomial of graphs containing triangles. By the properties, we prove the non-zero root of adjoint polynomial of Dn and Fn are single multiple.     

几类特殊图的(2,1)-全标号

研究了与频道分配有关的一种染色-(p,1)-全标号.通过在一个顶点粘结不同的简单图构造了几类有趣图,根据所构造图的特征,利用穷染法,给出了一种标号方法,得到了平凡和非平凡叶子图Gm,4、风车图K3t和图Dm,n的(2,1)-全标号数.(p,1)-全标号是对图的全染色的一种推广.     

图代数(Ⅰ)

设F是一个域。本文对于任意一个简单无向图G,定义了一个F代数R_G,F(称为G在F上的图代数),证明了图同构的充要条件是相应的图代数(作为F代数)同构。我们还讨论了上述定义及结论的若干推广。     

组合学的一个新概念--圆组合

1962年笔者在《数学通报》指出下述结果[1 ] :设n ,k为自然数 ,a ,b为实数或复数时 ,就有等价恒等式(a b) n =∑nk=0nk an-kbk,(二项式定理 )an bn =∑[n2 ]k=0( - 1 ) k nk (a b) n- 2k(ab) k,(等价二项式定理 )其中记号nk =n(n- 1 ) (n- 2 )… (n -k 1 )k!,nk =n(n -k- 1 ) (n -k- 2 )…(n- 2k 1 )k!.同时还发现等价恒等式的数字表、证明、性质以及应用上具有相似之处 .由于 nk 是组合记号 ,推测 nk 可能是另一组合记号 ,于是猜想 nk 中蕴藏着组合学的一个新概念 .40年韶光弹指过 ,近年笔者探讨孪生组合等式的问题[2 ,3,4] ,才能清楚地…     

含幺元的半格和群的Zappa-Sz'{e}p积上的同余

Let P = E G be a Zappa-Szp product of a semilattice E with an identity and a group G. In this paper, we first introduce the concept of congruence pairs for P , and then prove that every congruence on P can be described by such a congruence pair. In fact the congruence lattice on P is lattice-isomorphic to the set of all congruence pairs for P . Finally,we characterize group congruences on P .     

解析簇上非孤立奇点的C0-R_V-V(f) -充分性

给出了某类解析簇上具有非孤立奇点的函数芽f在某种等价关系下的C~0-R_V-V(f)-充分性及它的某些形变平凡性的充分条件.它推广了具有非孤立奇点的函数芽的R-Z-充分性的一个判别准则.