《对于r正则连通图的clique覆盖数刘建慧》
北京师范大学 硕士学位研究生毕业论文(86级理科) 论文题目:对于R一正则适通图的 Cligu复差数 基础数学 学科专业:研究方向:令数学 吴英 指导教师:研究生:刘建慧 数学 系(所):论文起止日期:1988-1989.
引言 图的clisne复盖和cligue划分间题最早出现 于六十年代,梦中心同题是求图的u复盖数 和C1:gme划分数。到回前为止,对一些特碑图形 的kgme划分数的求法已姨见成效,但对于digve 复盖数求过问题的研究进展却相当缓慢。因此 探讨chgv复盖表的求法是是有相当难度的,24 而也是具有重要意义的2作。本文仅对cligve复盖 赵求过向影的进一步研究做了一些爱试.图的cgve复盖讨n无同图G=<vCG)E(G)>,并皿假定G有限.无圈、无多重边。如果为 G的一个完全子图,则称为G一个clg,如果 1v(k)1=k.则好khk-odig,即阶为kKcligne 记作Kk。
因的1E[G)1=些,所以k,n不能同时为奇数,由止心 得Tk(n)=中(当k.n都为奇数时),(这样,当k取 定为奇数时,我到仅考虑n为偶数的情形.经过 如上分析.问题转化为当k23时.决定Tx(n)(n≥k2.且k.n不同时为等数)L。Cacetta 和 N.了.Pal- [man确定了Tz(n)和T4(n)。但对于k≥5时Tk(n) 的情况.却没有做任何讨地,参见[1].[2].本文继读讨忆k-正2连通图G,也即G∈Gk, 在51中分析了G中各clieme之间的相关位里并皿分 析了G的最小cMig心复盖才所含有的基本元素,使得对 G(k,n)中的某些特殊图形.
下载高清完整版