【作者】 董海燕；

【导师】 孙磊；

【作者基本信息】 山东师范大学 ， 应用数学， 2006， 硕士

【摘要】 在本文中,我们用[x]表示不大于实数x的最大整数,用[x]表示不小于实数x的最小整数。用[S]表示集合S中元素的个数。 除非特别指出,本文所讨论的图均为简单,有限,无向图。我们用V(G)和E(G)分别表示图G的顶点集和边集。对于任意顶点v∈V(G),用d_G(v)表示顶点v在图G中的度。用δ(G)和△(G)分别表示图G中顶点的最小度和最大度。G[V′]表示图G由顶点子集V′导出的子图,G[E′]表示图G由边子集E′导出的子图。K_n表示n个顶点的完全图。ω(G)表示图G的连通分支个数,κ(G)表示图G的连通度。α(G)表示图G的独立数,χ(G)表示图G的色数。本文所用术语与符号基本与文献[1]中一致。 随着图的染色问题在现实中被广泛应用,它逐渐成为众多学者研究的重要领域之一。在[2,3]中,起源于网络问题的点可区别边染色和邻点可区别边染色问题得到进一步研究。新的染色问题不断被提出,与该问题相关的,[4,5]中相继给出了(邻)点可区别全染色的定义及其几类简单图关于此染色的色数,并提出相关猜想。 张忠辅给出的(邻)点可区别全染色定义是这样的:设图G(V,E)为阶至少为2的简单连通图,k为正整数。函数f是从V(G)∪E(G)到C={1,2,…,k}的一个映射。 对于任意顶点u∈V(G),记C(u)={f(u)}∪{f(uv)|uv∈E(G)},(?)(u)=C-C(u)。 (1)对任意边uv,vw∈E(G),且u≠w,有f(uv)≠f(vw)。 (2)对任意边uv∈E(G),且u≠v,有f(u)≠f(v),f(u)≠f(uv),f(uv)≠f(v)。更多还原

【Abstract】 In this article , we use [x] for the maximum integer which is no more than the real number x , we use [x] for the minimum integer which is no less than the real number x . We denote by |S| the number of the elements in the set .All graphs considered are simple , finite and undirected . For a graph G , we denote the vertex set and the edge set of G by V（G） and E（G） , respectively. We use dc（v） for the degree of v in V（G） and A（G） for the maximum degree of G and δ（G） for the minimum degree of G . Let G[V’] denote the induced subgraph of G with vertex set V’ and G[E’] denote the induced subgraph of G with edge set E’. We denote by K_n the complete graph on n vertices . We use the symbols ω（G） and κ（G） to denote the number of components of G and the connectivity of G . The independence number of G is denoted by α（G） and the chromatic number of G is denoted by x（G） . For any undefined notation and terminology , we refer the reader to [1] .The definition of （adjacent） vertex-distinguishing total coloring by Zhang Zhongfu is as follows : Let G（V, E） is a simple and connected graph of which the order is at least 2 , k is an positive integer and f is the mapping from V（G）∪E（G） to C ={1,2,...,k}.For any vertex u 6 V（G） , denote C（u） = {f（u）}∪{f（uv）|uv ∈ E（G）} , C（u） = C- G（u） .（1） For any edge uv ,vw ∈ E（G） , and u ≠w , there is f（uv） ≠ f（vw） .（2） For any edge uv 6 E（G） , and u/t), there is f（u） ^ f（v） , f（u） ^ f（uv）, f（uv） ^ f（v） .（3） For any edge uv e E（G） , and u / v , there is C（u） ^ C（v） .（4） For any vertex u,v €. V（G） , and ?/?, there is C（it） 7^ C（v）.If （1） , （2） are satisfied , then / is called a A;-total coloring of graph G（in brief, it is noted as k-TC） .If （1） , （2） , （3） are satisfied , then / is called a A;-adjacent vertex-distinguishing total coloring of graph G （in brief , it is noted as k-AVDTC） .If （1） , （2） , （4） are satisfied , then / is called a k- vertex-distinguishing total coloring of graph G （in brief , it is noted as k-VDTC） .The total chromatic number of G isXt（G） = min{A;| G has k-TC}.The adjacent vertex-distinguishing total chromatic number of G is Xat{G) = min{k\ G has k-AVDTC}.The vertex-distinguishing total chromatic number of G is Xvt{G) = min{A;| G has k-VDTC}.The following results about adjacent vertex-distinguishing total coloring are right , apparently .For a simple connected graph G of order n （n = \V{G）\ > 2) , adjacent vertex-distinguishing total chromatic number Xat{G) exist , andXat（G） > A（G） + 1.If G（V, E） has two adjacent maximum degree vertices , thenXat（G） > A（G） + 2.The following conjecture is proposed by Zhang Zongfu in [4]:For a simple connected graph G of order n （n — \V{G）\ > 2) , thenXat（G）<A（G） + 3.In[4] , Zhang Zhongfu have obtained the adjacent vertex-distinguishing total chromatic number of some graphs such as path , circle , complete graph , 2-complete graph , star , fan , wheel and tree. These results are satisfied the conjecture .About vertex-distinguishing total coloring of graphs , Zhang Zhongfu have obtained the vertex-distinguishing total chromatic number of some graphs such as complete graph , 2-complete graph , double-star , fan , wheel in [5] . And he proposed the folowing conjecture :For a simple connected graph G of order n （n— \V（G）\ > 2） , thenKT（G） = max{t\t = min{^|（C^+1） > nd},5（G） < d < A（G）} . Let nd — nd{G) denote the number of all vertices of degree d in a graph G .The definition of fractional coloring is given in [6] by E.Scheinerman and D.Ullman, it is fractional generalization of coloring of graphs . Obtain every graph’s fractional chromatic number is iVP-hard .A mapping C from the collection C of independent sets of a graph G to the interval [0, 1] is a fractional-coloring if for every vertex x of G , we have Tlie<;,s.t.xGi C{I) > 1 ? The value of a fractional-coloring C is E/€c,5.t.ze/C（-0-The fractional chromatic number Xf（G） °f G ls the infimum of the values of fractional-coloring of G .Frational-coloring of a graph G has an equivalent definition . Xf{G） =\\m **L1 - inf 2^LJ. , Xb{G) is the 6-fold chromatic number of G . Assigns6—>oo b b bto each vetex of G a set of b colors , and adjacent vertices receive disjoint sets of colors , if all colors are draw from a palette of a colors , We say that G is a : 6-colorable . We sometimes refer to such a coloring as an a : 6-coloring . The least a for whiqh G has a : 6-coloring is the 6-fold chromatic number of G .Xb（G） — min{ a \ G has a : 6-coloring}.In this paper , about （adjacent） vertex-distinguishing total coloring of graphs, we have the following theorems .The graph with vetex set V（G） — {u;[} Vj\i = 1, 2, ■ ■ ?, m;j = 1, 2, ■ ? ?, n;m > n > 2} and edge set E（G） = {v,iVj\i = 1, ■ ? ?, m;1 < j < i} , We called "hypo-complete graph " . Denote by : G*mn .Theorem 2.1.1 Xat（G*m>n） = { ^[m + l,m> n>2.Add edge ViVn （i = 1, ? ? ?, n） to ^ of Cn — vxvi ■ ■ ■ vnv\ , denote by Add edge vxva （i = 1, ? ? ?, n） to Vi of Y^ , denote by Y^;? ■ ?;Add edge （i = 1, ■ ■ ■, n） to Vi of y^"1) ■ ? ? , denote by Y^ .... yji) is Qn .Theorem 2.1.2 XaMk)) = k + A （n > 3） . Theorem 2.1.3 x,t（>;（1）） = Xvt（Qn） = n （n > 5） .Add edges UjUj , UiVi+l , ??? , UjUj+fc , ??^,iiiui+（n₁） , （i = 1,2, ??■,n;/c = 0,1, ? ? ?, n — 1;where i + k > n + l , i + k with addition modulo n ） to both C\ = U1U2 ? ? -unui（n > 3） and C2 = ^1^2 ? ■ ■^n^i（" > 3） , denote these graphsTheorem 2.1.4 Where n > 4 and n = 0{mod2) ,Theorem 2.1.5 Where n > 4 and n = I（raod2） , （1） XatiCU) = 5, . ..（2）Where 1 <k<n-l,k + 5< Xat（Cg+x>） < k + 6 .Add edges UiV^i and UiVi+i （i = 2,3, ? ? ?, n — 1） to Ui of <5n（" > 3）;Add edges u\V2 and uaun to iti;Add edges uni>n_i and ???! to un , denote this graph by Q*n .Theorem 2.1.6 Xat{Q*n) = 7 （n > 3） .Doubble edge ViVi+i（ where % — n ,it is vnv{） of Cn = vxv2 ? ■ ■ vnv\（n > 3） , add vetex u^ （i — 1,2, ? ? ?, n） in outside edge , denote this graph by Hn .Theorem 2.1.7 Xat{Hn) = 6 （n > 3）Add vetex ty, （i = 1,2, ? ? ■, n） in edge V{Vi+i （ where i = n , it is vnv\） of i/n（n > 3） , denote this graph by P* .Theorem 2.1.8 Xt{P$ = Xat（P*n） = 5 （n > 3） .Add edges WjiXj （z = 1,2, ■ ? ?, 2n） to each vertex Vi of Cin = （n > 2） , also add edges UjUj+i （i = I（mod2）） ,/denote this graph byTheorem 2.1.9 xat（W^） = 5 （n > 2） .In this paper , about fractional coloring of graphs , we have the following theorems .Let o and b be positive integers with a > 26 . Let Ga,b be the graph’6];with vertex set.V{Ga,b)={ v0 , vx , ■ ■ ■ , ua_i };The neighbors of vertex v{ are { vi+b, vi+b+i , ? ? ? , vi+a+b } with addition modulo a .Graph G is called vertex-transitive ’6’: for every pair of vertices u , v €V（G） there exists an automorphism of G with tt（u）=v .Proposition 2.2.1? xf（Ga,b） = f;Xb（Ga,b） = a .Proposition 2.2.2^ For any graph G , Xf（G） > ^ . Furthmore, if G is vertex-transitive , then equality hold .Lemma 2.2.3 For any vertex v e V{Ga>b) , ^ < Xf（Ga,b - v） < f .Theorem 2.2.4 Where a = kb , k e Z and k > 2 , there is Xf（GaJ, - v） = f .Theorem 2.2.5 Where a = 26 + 1 , there is Xf（Ga,b - v） = ^ .In Gajb graph ,let e^ = （i>j, Vi+b） , z = 0,1, ? ? ?, a — 1 . i + 6 with addition modulo a .Theorem 2.2.6 Where e^e{ , there is Xf（Ga,b - e） = f . Lemma 2.2.7 s=± < Xf（Ga,b - e{） < f , i = 0,1, ■ ? ?, a - 1 .Theorem 2.2.8 Where a = kb , k e Z and A;> 2 , there is X/（Ga,b - ei） = f , i = 0,1, ? ? ?, a - 1 .Theorem 2.2.9 Where a = 26 + 1 , there is Xf（Ga,b - e{） = ^, i = 0,1, ? ? ■, a — 1 .Theorem 2.2.10 Where a - kb , k e Z and A;> 2 , there is Xf（Ga,b U （t>j, Uj）） = | for arbitrary nonadjacent vertices V{ , Vj in.Gaij, .Theorem 2.2.11 x/（Ga,hu（^ , vi+1）） > xf{Gajb) , i = 0,---,a- 1更多还原