图的D(2)-点可区别一般边染色

引入了图的D(β)-点可区别一般边染色,并对β=2的情形做了讨论,得到了路,圈,星,双星,扇,轮的D(2)-点可区别一般边色数,对于2距离色数等于3及4的图的D(2)-点可区别一般边色数做了探讨,特别研究了具有稳定2距离4着色的图的D(2)-点可区别一般边染色.文中提出了一个相关猜想和一个公开问题.     

C_m·S_n的D(2)-点可区别边色数

对阶数不小于3的连通图G(V,E),设α,β为正整数,令映射f:Ef{1,2,…,α},若u,v∈V(G),1≤d(u,v)≤β,有C(u)≠C(v),则称f为G的一个α-D(β)-点可区别的边染色,简记为α-D(β)-VDPEC,对一个图进行α-D(β)-点可区别的边染色,所需的最少的颜色数称为图G的D(β)-点可区别的边色数,记为χ′β-vd(G),其中d(u,v)表示两个点u,v之间的最短距离.得到了Cm.Sn的D(2)-点可区别边色数.     

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

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

图的点可区别的分数边染色数

讨论了图的点可区别的边染色数在分数图论的拓展,采用分数图论中超图的a:b-染色方法,证明了邻点可区别的分数边染色数与分数边染色数的等价性,同时进一步推导出经典图论中几类点可区别的边染色数概念如κ-D(β)-点可区别的边染色数、点可区别的边染色数和边染色数也在分数图论的拓展下具有等价性.     

Pkn(k≡2(mod3))的D(2)-点可区别全染色

图的D(β)-点可区别全染色就是指图G的一个正常全染色且使得距离不大于β的任意两点有不同的色集合.讨论了幂图P_n~k当k≡2(mod3)时的D(2)-的点可区别全染色,并且根据P_n~2与C_n~2图的结构关系获得C_n~2的邻点可区别的全染色数.     

一类正则循环图的Cartesian积图的D(β)-点可区别VI-全染色及I-全染色

设G是简单图,若图G的全染色f满足:1)(?)uv,vw∈E(G),有f(uv)≠f(vw);2)(?)uv∈E(G),u≠v,有f(u)≠f(v);3)(?)u,v∈V(G),0相似文献   

一类正则循环图的Cartesian积图的D(β)-点可区别Ⅵ-全染色及Ⅰ-全染色

设G是简单图,若图G的全染色f满足:1)(V)uv,vw∈E(G),有f(uv)≠f(vw);2)(V)uv∈E(G),u≠v,有f(u)≠f(v);3)(V)u,v∈V(G),0＜d(u,v)≤β,有S(u)≠S(v),这里色集合S(u)={f(u)}∪{f(uv) |uv∈E(G)}.则称f是图G的一个D(β)-点可区别Ⅰ-全染色.若f只满足条件1)和3),则称f是图G的一个D(β)-点可区别Ⅵ-全染色.研究了当β=1,2时一类正则循环图与圈的Cartesian积图的D(β)-点可区别Ⅵ-全色数和D(β)-点可区别Ⅰ-全色数,并讨论了正则图的D(β)-点可区别Ⅵ-全色数和D(β)-点可区别Ⅰ-全色数的上界.     

距离限制下的点可区别全色数的一个上界

图G的-个正常全染色被称作D(β)-点可区别全染色,如果G中距离不超过β的任意两点有不同的色集,其中,每个点的色集由该点和其邻边的颜色所组成.本文得到了图G的-个D(β)-点可区别全色数的新上界.     

图的D(2)点可区别星边色数的一个上界

提出了图的D(β)点可区别星边染色及D(β)点可区别星边色数的概念,并用Lovasz局部引理证明了在β=2时,若G=(V,E)是一个最小度为δ(G)>3的简单无向图,则X_(2-vds)(G)≤24△2/3]。     

图的一般邻点可区别均匀边染色和均匀全染色

提出了一般邻点可区别均匀边染色和全染色的新概念,研究了路P_n、圈C_n、星S_n、扇F_n、轮W_n、完全二部图K_(m,n)、2维平面网格图P_m×P_n的一般邻点可区别均匀边染色和全染色,具体给出这些图的一般邻点可区别均匀边染色和全染色指标.     

图类αK_a∪βCP(b)中的一类特殊整谱图

图G是一个简单图,图G的补图记为G,如果G的谱完全由整数组成,就称G是整谱图.鸡尾酒会图CP(n)=K_(2n)-nK2(K_(2n是完全图)和完全图K_a都是整谱图.μ_1表示图类αK_a∪βCP(b)的一个主特征值,确定了当μ_1=2a并且a-1>2b-2时,图类αK_a∪βCP(b)中的所有的整谱图.     

D(β)-vertex-distinguishing total coloring of graphs

A new concept of the D(β)-vertex-distinguishing total coloring of graphs, i.e., the proper total coloring such that any two vertices whose distance is not larger than β have different color sets, where the color set of a vertex is the set composed of all colors of the vertex and the edges incident to it, is proposed in this paper. The D(2)-vertex-distinguishing total colorings of some special graphs are discussed, meanwhile, a conjecture and an open problem are presented.     

图类^-αKα∪βCP（b）中的整谱图

设图G是一个简单图,图G的补图记为^-G,如果G的谱都是整数,就称G是整谱图．鸡尾酒会图CP（n）=K2n-nK2（K2n是2n阶完全图）和完全图Kα都是整谱图．本文确定了图类^-αKα∪βCP（b）中的所有整谱图．     

极大饱和图D（n,k）的极值性质及圈唯一性

本文证明了极大饱和图Ｄ（ｎ，ｋ）的一个极值性质：在与Ｄ（ｎ，ｋ）具有相同度序 所有图中，唯有Ｄ（ｎ，ｋ）含有最少的Ｋ３子图，并由此推出，在几乎正则图的范围内，ｋ个完全图之并及完全ｋ部多分图均是圈唯一的。本文还用图谱方法，证明了完全二分图Ｋｍ，ｎ的圈唯一性。     

Line graphs of complete multipartite graphs have small cycle double covers

It has been shown by MacGillivray and Seyffarth (Austral. J. Combin. 24 (2001) 91) that bridgeless line graphs of complete graphs, complete bipartite graphs, and planar graphs have small cycle double covers. In this paper, we extend the result for complete bipartite graphs, and show that the line graph of any complete multipartite graph (other than K_1,2) has a small cycle double cover.     

Distance Integral Complete Multipartite Graphs with s=5, 6

Let D(G) = (dij )n×n denote the distance matrix of a connected graph G with order n, where dij is equal to the distance between vertices vi and vj in G. A graph is called distance integral if all eigenvalues of its distance matrix are integers. In 2014, Yang and Wang gave a su?cient and necessary condition for complete r-partite graphs Kp1,p2,··· ,pr =Ka1·p1,a2·p2,··· ,as···ps to be distance integral and obtained such distance integral graphs with s = 1, 2, 3, 4. However distance integral complete multipartite graphs Ka1·p1,a2·p2,··· ,as·ps with s>4 have not been found. In this paper, we find and construct some infinite classes of these distance integral graphs Ka1·p1,a2·p2,··· ,as·ps with s = 5, 6. The problem of the existence of such distance integral graphs Ka1·p1,a2·p2,··· ,as·ps with arbitrarily large number s remains open.     

完全多部图的无符号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.     

The crossing number of K1,3,n and K2,3,n

In this article, we will determine the crossing number of the complete tripartite graphs K_1,3,n and K_2,3,n. Our proof depends on Kleitman's results for the complete bipartite graphs [D. J. Kleitman, The crossing number of K_5,n. J. Combinatorial Theory 9 (1970) 315-323].