3-调和的5-圈图

设v1，v2，v3，…，vn是图G的n个顶点，（d（v1），d（u2），d（u3），…，d（vn））^T是图G邻接矩阵A的特征向量，则称G是调和图，其中d（vi）表示顶点弘的度．1—4圈的调和图已经确定，本文确定了所有的3-调和的5-圈调和图．     

平面图点荫度的一个局部条件

图G的点荫度va(G)是指V(G)的最小划分数,使得每个点划分集的导出子图是一个森林.众所周知,平面图G的点荫度至多为3.2008年,Raspaud和王维凡证明了:若G是不含κ-圈(κ∈{3,4,5,6})的平面图,则va(G)≤2.本文推广了上述结果,得到了点荫度至多为2的一个局部条件,即若平面图G的每一个点都不同时与3-圈、4-圈、5-圈和6-圈关联,则va(G)≤2.     

轮图的广义Mycielski图的邻强边色数

设图 G(V,E)为简单图 ,V(Mn(G) ) |{ v0 1,v0 2 ,… ,v0 p;v11,v12 ,… ,v1p,… ,vn1,vn2 ,… ,vnp}E(Mn(G) ) =E(G)∪ { vijv(i+ 1) k|v0 jv0 k ∈ E(G) ,1≤ j,k≤ p ,i =0 ,1,… ,n - 1}称 Mn(G)为 G的 n广义 Mycielski图 ,n为自然数 .本文得到了轮的广义 Mycielski图的临强边色数 .     

边覆盖临界图的一些性质

设G是一个简单图,其顶点集为V(G)而边集为E(G),S∈E(G)称为 G的一个覆盖,如果由S导出的子图为G的一个生成子图. G的边覆盖色数χ'c(G)是E(G,)所能划分成的最大边覆盖数.已知δ-1 ≤χ'c(G)≤δ,由此将χ'c(G)=δ的图称为CI类图,否则称为CII类图.若G是连通CII类图,且G不是完全图,对任意的u,u∈V(G),e=uv( )E(G),都有χ'c(G+e)＞χ'c(G)成立,则称G为边覆盖临界的.本文研究了边覆盖临界图的一些性质.即若G为边覆盖临界图,则对任意的u,v∈V(G),若e=uv( )E(G),总存在w∈{u,v},有d(w)≤2δ-2,且w至少与max{d(w)-δ+1,3d(w)-4δ+4}个最小度顶点相邻.     

哈密顿线图的一个充分条件

对于图G的任意边e=uv,边的度定义为d(e)=d(u)+d(v),其中d(u)和d(v)分别为顶点u和v的度.本文的主要结果是: 设G是几乎无桥的p≥2阶简单连通图,且G(?)K_(1,p-1),若对任意相距为2的两边e_1和e_2,d(e_1)+d(e_2)≥2p-6,则G有一个D—闭迹,从而G的线图L(G)是哈密顿的.     

若干图的广义Mycielski图的边色数

设图G(V,E)为简单图,V(Mn(G))={v01,v02,…,v0p;v11,v12,…,v1p;…,vn1,vn2,…,vnp}EMn(G))=E(G)∪vijv(i+1)kv0 jv0k∈E(G),1 j,k p,i=0,1,…,n-1称Mn(G)为G的n串广义M ycielsk i图,其中n为自然数,V(G)={v01,v02,…,v0p}.本文得到了路、圈、扇、轮、星图的广义M ycielsk i图的边色数.     

边色数的分类及其有关性质

设图G为简单连通图,由Vizing定理知:Δ(G)≤x′(G)≤Δ(G) 1,其中Δ(G)表示图G的最大顶点次,x′(G)为图G的边色数。若x′(G)=Δ(G),则称G为第一类图,记为G∈C~1;若x′(G)=Δ(G) 1,则称G为第二类图,记为G∈C~2。其他图论术语见一般参考书。一边e(或者顶点v)称为临界的,如果成立x′(G)>x′(G\e)(或者x′(G)>x′(G\v))。图G称为是临界的,如果G∈C~2,且G的每一边是临界的。对于v∈V(G),令d~*(v)=|{u|(v,u)∈E(G)且d(u)=Δ(G)}|。设F={u|d(u)=Δ(G),u∈V(G)},记G_Δ=G[F]。令图G_Δ的圈秩数为b(G_Δ)。     

广义Mycielski图的邻强边色数和邻点可区别全色数的两个上界

对简单图G,|V(G)|=p,n是自然数,Mn(G)被称为图G的广义Mycielski图,如果V(Mn(G))={v01,v02,…,v0p;v11,v12,…,v1p;…;vn1,vn2,…,vnp},E(Mn(G))=E(G)∪{vijv(i+1)k|v0jv0k∈E(G),1≤j,k≤p,i=0,1,…,n-1}.文中针对简单图G与它的广义Mycielski图之间的关系,给出了G的广义Mycielski图的邻强边色数和邻点可区别全色数的两个上界.     

关于图的L(d,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.此文研究了作为L(2,1)-标号问题的推广的L(d,1)-标号问题,并得出了平面三角剖分图、立体四面体剖分图、平面近四边形剖分图的L(d,1)-标号的上界,作为推论证明了对上述几类图该猜想成立.     

关于蕴含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－可图的序列判别准则。     

若干图的卡氏积的距离谱和距离能量(英文)

G是顶点集为{v_1,v_2,…,v_n}的连通简单图,G_1,G_2,…,G_n是有限图。联并图G[G_1,G_2,…,G_n】是按如下方式在G_1UG_2U…UG_n上加边而成的图:在G_i和G_j之间的任何两个顶点间加边,若v_i和v_j在G中相邻.[7]给出了两个距离正则图的卡氏积的距离谱.本文计算了联并图和距离正则图的卡氏积及两个联并图的卡氏积的距离谱.在此基础之上,我们得到了两个利用联并图与非同谱距离正则等能量图作卡氏积及联并图作卡氏积构造非同谱等距离能量图族的方法.     

Heavy cycles in 2-connected triangle-free weighted graphs

A weighted graph is one in which every edge e is assigned a nonnegative number, called the weight of e. The sum of the weights of the edges incident with a vertex v is called the weighted degree of v, denoted by dw(v). The weight of a cycle is defined as the sum of the weights of its edges. Fujisawa proved that if G is a 2-connected triangle-free weighted graph such that the minimum weighted degree of G is at least d, then G contains a cycle of weight at least 2d. In this paper, we proved that if G is a2-connected triangle-free weighted graph of even size such that dw(u) + dw(v) ≥ 2d holds for any pair of nonadjacent vertices u, v ∈ V(G), then G contains a cycle of weight at least 2d.     

图的度和与扩路

本文讨论了两顶点的度和与路可扩之间的关系,得到了如下结果:设G是n阶图,如果G中任意一对不相邻的顶点u,v满足d(u)+d(v)≥n+n/k(2≤k≤n-2),则G中任意一个满足k+1≤|P|相似文献   

点度与图的上可嵌入性

本文证明了:(1) 设G是2-连通简单图,且不含K_3,若对任意一对距离为2的点u,u,有max{d(u),d(u)}>n/3-1,其中n=|V(G)|,则G是上可嵌入的,且条件中不等式的界"n/3-1"是不可达的;(2) 设G是3-连通简单图,若对任意依次相邻的三点u,u,W,有max{d(u),d(u),d(w)}≥n/6+1,其中n=|V(G)|,则G是上可嵌入的,且条件中不等式的界"n/6+1"是最好的.     

关于图的L(3,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 .本文将L( 2 ,1 ) 标号问题推广到更一般的情形即L( 3,2 ,1 ) 标号问题 .我们首先定义了图G的顶点 3 着色及图的 3 色数 χ3 (G)等有关概念 ,并推导出 3 色数 χ3 (G)的上界 ;然后根据 χ3 (G)与λ3 (G)的关系 ,得出了对一般图G ,有λ3 (G) ≤ 3maxH Gδ(H) (Δ2 -Δ 1 )这一一般关系式 ;最后证明了对一般平面图G ,有λ3 (G)≤ 1 5(Δ2 -Δ 1 ) ,并得出了其它几类平面图的λ3 (G)的上界 .     

不含三角形图的正常染色路和正常染色圈

图G为边染色图,对G中的任一顶点v,定义v的色度dc（v）：G中与顶点v相关联的边中不同染色的数目.用δc（G）表示图G的最小色度,即δc（G）=min{dc（v）：v∈G}.若图G为不含三角形的边染色图,且δc（G）≥2,则G含长为4d-2的正常染色路或长至少为2d-2的正常染色圈.     

K3-free图的线图的哈密顿性

设G是一个简单图，Gi G，G1在G中的度定义为d（Gt）=∑v∈v（c）d（v），其中d（v）为v在G中的度数。本文的主要结果是：设G是n≥2阶几乎无桥的简单连通K3-free图，且G≌k1,n-1、Q1和Q2，若对G中任何同构于四个顶点路的导出子图I有d（I）≥n＋2，则G有一个D-闭迹，从而G的线图L（G）是哈密顿图。     

整数距离图G(D_(m,k,2))的点荫度

图G的点荫度va(G)是顶点集合V(G)能划分成的这样一些子集的最少数目,其中任一子集的点导出子图都是森林.整数距离图G(D)以全体整数作为顶点集,顶点u,v相邻当且仅当|u-v|∈D,其中D是一个正整数集.对于m2k≥2,令D_(m,k,2)=[1,m]\{k,2k}.该文得出了整数距离图G(D_(m,k,2))的点荫度的几个上、下界;进而,对于m≥4,有va(G(D_(m,1,2)))=[(m+4)/5];对于m=10q+j,j=0,1,2,3,5,6,有va(G(D_(m,2,2)))=[(m+1)/5]+1.     

<Emphasis Type="Italic">p</Emphasis>-adic properties of division polynomials and elliptic divisibility sequences

For a fixed rational point P E (K) on an elliptic curve, we consider the sequence of values (F_n (P))_n1 of the division polynomials of E at P. For a finite field we prove that the sequence is periodic. For a local field we prove (under certain hypotheses) that there is a power q=p^e so that for all m1, the limit of exists in K and is algebraic over We apply this result to prove an analogous p-adic limit and algebraicity result for elliptic divisibility sequences.Mathematics Subject Classification (1991): 11G07, 11D61, 14G20, 14H52The authors research supported by NSA grant H98230-04-1-0064.