学位论文 > 优秀研究生学位论文题录展示

图的群着色数

作　者: 张娟
导　师: 李相文
学　校: 华中师范大学
专　业: 运筹学与控制论
关键词: 群着色数最大度连通图笛卡尔积图度序列着色问题
分类号: O157.5
类　型: 硕士论文
年　份: 2011年
下　载: 11次
引　用: 0次
阅　读: 论文下载

内容摘要

用G=(V,E)表示一个图,A代表一个非平凡的阿贝尔群,用F(G,A)表示所有函数f:E(G)→A组成的集合,用D表示E(G)的定向。我们说G是A-可着色的当且仅当对于每一个f(?)F(G,A都存在着一个A-着色c:V(G)→A,使得对每条边e=xy(?)E(G)(假设边的定向是由x发向y的),c(x)-c(y)(?)f(w).如果G代表一个图,我们定义它的群着色数xg(G)是在定向D下,使得G是A-可着色的,|A|≥m的最小的m值。我们这篇论文主要涉及到的是群着色数和一些给出的结果。令k=maxHδ(H),其中H是图G的任一支撑子图,我们可以得出：Xg(G)≤k+1.简单图G和H的笛卡尔乘积记作图G口H,这个图的顶点集合是V(G)×V(H),它的边集是有所有的这些序列对(u1,v1)(u2,v2)组成的,如果满足以下两种情况：(1)u1u2(?)E(G),同时v1=v2;(2)v1v2(?)E(H),同时u1=u2.所以,我们可以验证Xg(Pn□Pm)=3,Xg(Pn□Cm)=4,Xg(Cn□Cm)≤4,Xg(Qn)≤n-1.本文主要证明的结论是：(1)令数△≥3,图G满足：△(G)≤△,并且K△+1(?)G,那么有Xg(G)≤△;(2)对任意简单图G1和G2有：Xg(G1□G2)≤max{Xg(G1)+1,Xg(G2)+1}.

全文目录

中文摘要  5-6
Abstract  6-8
1. 前言  8-13
  1.1 学术背景和意义  8
  1.2 概念和符号说明  8-10
  1.3 图群着色相关问题的研究现状  10-11
  1.4 本文主要工作概述  11-13
2. 预备知识  13-16
  2.1 补充概念  13
  2.2 已知结论  13-16
3. 主要结论  16-25
  3.1 主要结论证明所需引理及其推论  19-21
  3.2 主要结论证明  21-25
结束语  25-26
参考文献  26-28
致谢  28

图的群着色数

内容摘要

全文目录

相似论文