一类完全三部图的色唯一性

用P(G,λ)表示简单图G的色多项式.设G是一个给定的简单图,若对任意简单图H,当P(H,λ)=P(G,λ)时都有H和G同构(记为H≌G),则称图G是色唯一的.本文证明了以下结果:设n,k,△都为非负整数,其中k≥0,△∈{4,5},若n≥1/3k~2+1/3△~2-1/3k△-1/3k-1/3△+4/3,则完全三部图K(n,n+△,n+k)是色唯一的.同时还给出了一个猜想.     

高度图的关联色数

为了解决强边着色猜想,1993年,Brualdi和Massey（Discrete Math. (122)51-58)引入了关联着色概念,陈东灵等证明了对于△（G）=n-2的图G.inc(G)≤△(G) 2,其中n是G的阶数,本将进一步探讨在什么条件下,它的关联色数肯定是△（G） 1,又在什么条件下,肯定是△（G） 2。     

色指数临界图的一些新结论

图的边色数是指对图的边进行染色使得任意两相邻边染不同的颜色所需要的最少的颜色数.1965年,Vizing证明了任意最大度为△的图的边色数或者是△或者是△+1.若G是连通的,且G的每一条边e均有X′(G-e)相似文献   

边色数分类的两个结果

设图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;A.J.W.Hilton提出了如下猜想[1]:如果G是简单图,且满足:(ⅰ)△(G)>2/3(|V(G)|-3),(ⅱ)δ(G_△)≤1。则G∈C~1。本文的目的是围绕着这一猜想,得出了两     

图与其Mycielski图关联色数的关系

本文证明了对n阶图G,若其最大度△(G)的2倍不等于n,且G的关联色数等于△(G) 1,则M(G)的关联色数为△(M(G)) 1．同时还研究了树和完全二部图的Mycielski图的关联色数．文末提出了M(G)的关联色数猜想,其中M(G)为图G的Mycielski图．     

含有大的悬挂树图的Ramseygoodness结论(英文)

设H是阶为n的连通图.在H的某一个顶点上悬挂一棵阶为j的树,得到图H_j,用H_j表示这样的图形族.本文证明:当j充分大时,有r(G,H_j)=(x(G)-1)(n+j-1)+s(G),其中x(G),s(G)分别表示图G的色数和色数剩余.     

边覆盖临界图的一些性质

设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的正常边着色，如果此种边着色使得该图没有2—色的圈，那么这种边着色被称为是G的无圈边着色．用d(G)表示图G的无圈边色数，即G的无圈边着色中所使用的最小颜色数．Alon N，Sadakov B and Zaks A在[1]中有如下结果：对于围长至少是2000△(G)log△(G)的图G，有d(G)≤△ 2，其中△是图G的最大度．我们改进了这个结果，得到了如下结论：对于围长至少是700△(G)log△(G)的图G，有d(G)≤△ 2．     

第一类图的若干充分性条件

1964年,V.G.Vizing[2]证明了简单图 G 的边色数 x′(G)满足△(G)≤x′(G)≤△(G)+1.其中△(G)为图 G 的最大度.若x′(G)=△(G),则称 G 为第一类图,并简记为 G∈C~1;若 x′(G)=△(G)+1 则称 G 为第二类图,并简记为 G∈C~2.     

关于完全t部图的色唯一性

设P(G,λ)是图的色多项式。如果对任意使P(G,λ)=P(H,λ)的图H都与G同构,则称图G是色唯一图.这里通过比较t 1色类的色划分数目,讨论了由Koh和Teo在文献[1]中提出的问题(若|ni-nj|≤2,当min(n1,n2,…,nt)充分大时,完全t部图K(n1,n2,…,nt)是否是色唯一图?)。改进了文献[5]中的结果。证明了若Σ1≤i≤ta2i=T,min{n a1,n a2,…,nt at,n-1}≥(T 1)/2,则K(n a1,n a2,…,n at)是色唯一图(其中ai是实数,n ai是正整数)。从而证明了若|ni-nj|≤k(i,j=1,2,…,t),min{n1,n2,…,nt}≥tk2/8 1,则K(n1,n2,…,nt)是色唯一图。     

图的点可区别Ⅳ-全色数的一个上界

δ和△分别表示图G的最小度和最大度,利用概率方法研究点可区别IV-全色数的上界,证得如果δ≥2,δ≥61n△,n≤([16Δ(Δ-1)]~(δ-1))/(96π·δ~(δ+2)·(Δ+1)),那么x_(vt)~(iv)(G)≤16Δ(Δ-1).     

Hosoya指标在一个闭区间的一类树的刻画(英文)

Let n and d be two positive integers.By B_n,d we denote the graph obtained by identifying an endvertex of path P_d with the center of star S_n-d+1,where n ≥ d + 1.By C_n,d we denote the graph obtained by identifying an endvertex of P_d-1 with the center of Stare S_n-d,and the other endvertex of P_d-1 with the center of S₃ where n ≥ d + 3.By E_n,d,k we denote the graph obtained by identifying the vertex v_k of P(v₁ - v₂ - ··· - v_d+1) with the center of S_n-d.In this paper,we completely characterize all trees T which have diameter at least d（d ≥ 3） and satisfy the following conditions:（i） Z(B_n,d) ≤ Z（T） ≤ Z(E_n,d,3) for n = d + 3;（ii） Z(B_n,d) ≤ Z（T） ≤ Z(C_n,d) for n ≥ d + 4.     

最大度不小于3的图的星全色数的一个上界

对圈、扇和轮作了简单的剖分,得到了其剖分图的星全色数,并运用Lovasz局部引理证明了若G(V,E)是一个最大度为△≥3的简单无向图,则Χ_(st)(G)≤22Δ~2.     

D(2)-点可区别正常边色数的一个上界

图G的D(β)-点可区别正常边染色是指G的一个正常边染色f使得对任意两点u,v∈V(G),0相似文献   

完全多部图的无符号Laplacian特征多项式(英文)

For a simple graph G,let matrix Q（G）=D（G） + A（G） be it’s signless Laplacian matrix and Q G （λ）=det（λI Q） it’s signless Laplacian characteristic polynomial,where D（G） denotes the diagonal matrix of vertex degrees of G,A（G） denotes its adjacency matrix of G.If all eigenvalues of Q G （λ） are integral,then the graph G is called Q-integral.In this paper,we obtain that the signless Laplacian characteristic polynomials of the complete multi-partite graphs G=K（n₁,n₂,···,n_t）.We prove that the complete t-partite graphs K（n,n,···,n）t are Q-integral and give a necessary and sufficient condition for the complete multipartite graphs K（m,···,m）s（n,···,n）t to be Q-integral.We also obtain that the signless Laplacian characteristic polynomials of the complete multipartite graphs K（m,···,m,）s1（n,···,n,）s2（l,···,l）s3.     

完全多部图与完全图Kronercker积的点参数研究

若G1和G2是两个图,G1和G2的Kronecker图定义为V (G1×G2)= V (G1) × V (G2 E(G1 × G2)= {(u1,v1)(u2,v2)。在本文中,我们计算了p-部完全图 m1,m2,...,mp 和完全图Kn 的Kronecker积的顶点参数,m1 ≤ m2 ≤ ... ≤ mp,2 ≤ p ≤ n, and n ≥ 3 ,扩展了Mamut和Vumar的相关结论[Inform. Process. Lett. 106(2008)258-262].     

半正的分数阶微分方程(n-1,1)-型积分边值问题的多个正解

采用Riemann-Liouville分数阶导数,研究了半正的分数阶微分方程(n-1,1)-型积分边值问题,获得了参数λ的一个区间,使得λ落在这个区间的时候,该半正的分数阶微分方程边值问题有多个正解.     

Kronecker乘积图的超连通性(英文)

设G1和G2是两个连通图,则G1和G2的Kronecker积G1×G2定义如下:V(G1×G2)=V(G1)×V(G2),E(G1×G2)={(u1,v1)(u2,v2):u1u2∈E(G1),v1v2∈E(G2)}.我们证明了G×Kn(n≥4)超连通图当且仅当κ(G)n>δ(G)(n 1),其中G是任意的连通图,Kn是n阶完全图.进一步我们证明了对任意阶至少为3的连通图G,如果κ(G)=δ(G),则G×Kn(n≥3)超连通图.这个结果加强了郭利涛等人的结果.     

一种场站设置问题中的几个结论

本文研究如下一种场站设置问题:设S是欧空间E~m中由有限个点A_1,A_2,…,A_n组成的集合.d(A_i,A_j)表示点A_i和A_j之间的距离.令σ(S)=Σ_(1≤i相似文献   

退化图中的子图计数问题研究

令G表示n个顶点的图,如果G的每个子图中都包含一个度至多为k的顶点,则称G为k-退化图.令N(G,F)表示G中F子图的个数.主要研究了k-退化图中完全子图和完全二部子图的计数问题,给出了计数的上界以及相应的极图.首先,证明了Ν(G,K_t)≤(n-k)(k t-1)+(k t).其次,如果s,t≥1,n≥k+1且s+t≤k,我们证明了Ν(G,K_s,t)≤{(k s)(n-s s)-1/2(k s)(k-s s),t=s,(k s)(n-s t)+(k t)(n-t s)-(k t)(k-t s),t≠s.此外,还研究了在最大匹配和最小点覆盖为给定值的情况下,图G中的最大边数.记v(G),K(G)分别为图G的最大匹配数和最小点覆盖.证明了当v(G)≤k,K(G)=k+r且n≥2k+2r²+r+1时,有e(G)≤(k+r+1 2)+(k-r)(n-k-r-1).