广义Petersen图的2-hued着色

设正整数k,r>0,图G的一个(k,r)-着色是用k种颜色对顶点集V(G)进行正常着色,使得对任意v∈V(G),至少连接min{d_(G)(v),r}种不同颜色的顶点.图G的r-hued着色数,记为χ_(r)(G),是使得图G具有(k,r)-着色的最小正整数k.已知广义Petersen图的2-hued着色数是3或4,分别刻画2-hued着色数为3或4的广义Petersen图.

一类广义Petersen图的L(2,1)-标号

图G的L(2,1)-标号是从图G的顶点集到非负整数集的一个映射f:V(G){0,1,2,…},它满足对任意两个顶点x,y,当d(x,y)=1时,|f(x)-f(y)|≥2;当d(x,y)≥2时,|f(x)-f(y)≥1.研究了n≡0(mod3)的广义Petersen图G=P(n,t)的L(2,1)-标号数l2,1(G),得到当t≡0(mod3),5≤l2,1(G)≤8,否则l2,1(G)

一类广义Petersen图的2-距离染色

图G(V,E)的2-距离染色是指正常的顶点染色,且满足距离不大于2的任意两个顶点染不同的颜色.研究了一类广义Petersen图P(n,2)的2-距离染色,并确定了P(n,2)的2-距离色数.

广义Petersen图的最小点覆盖集

点覆盖问题是一个著名的NP完全问题.本文对广义Petersen图P(n,2)的精确最小点覆盖数进行研究,讨论并证明了广义Petersen图P(n,2)的最小点覆盖数,给出了最小点覆盖集的构造方法.

s不超过6的无标号(n,n/2+s)-奇图的计数

一个图称为(n,m)-图,若|V(G)|=n且|E(G)|=m.一个奇图是指每个点的度都是奇数的图.给出了一种新的图同构的定义,计算并给出了不同构无标号(n,n/2+5)-奇图的结果,并对s=4,6给出了不同构无标号(n,n/2+s)-奇图的完整结果.

广义彼得森图的2-可扩性

本文证明了当k≥3,n≠2k,3k时,广义彼得森图GP(n,k)中的任意两条不邻接边都包含在GP(n,k)的1-因子中。

对Ramsey图(3,10)的初步探讨

用二色图的递阶生成方法,充分讨论了K39(3,10)的构造,并推想该图是(3,10)Ramsey图.