扇图的一般Pebbling数

图G的一个一般pebbling移动是从一个顶点上移走p(p≥2)个pebble,而把其中的一个pebble移到与其相邻的一个顶点上.图G的一般pebbling数f gl(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列一般pebbling移动把一个pebble移到图G的任意一个顶点上.本文研究了扇图的一般pebbling数.     

路的最优3-pebbling数

图G的一个pebbling移动是从一个顶点移走两个pebble,把其中的一个pebble移到与其相邻的一个顶点上.图G的最优3-pebbling数f'3(G)是最小的正整数,使得把n个pebble恰当地放置在G的顶点上,总可以通过一系列pebbling移动把三个pebble移到任何一个指定的顶点上.本文给出了路的的最优3-pebbling数的结论及其证明.     

直径粘接图的pebbling数

图G的pebbling数f(G)是指在一个图G的顶点上以任意方式放置若干个pebble数目的最小值,满足通过一系列的pebbling移动使得任一指定目标顶点能得到一个pebble,而pebbling移动是从一个顶点处移走两个pebble并把其中的一个移到与其相邻的一个顶点上.文章定义了将两个图的直径端点之一粘接生成的一类粘接图,主要计算了一些粘接图的pebbling数,发现了两类满足pebbling数直径下界的图.     

广义Halin图的竞争数

对于任意图G,G并上足够多的孤立顶点就为某个无圈有向图的竞争图.这样加进来的孤立顶点的最少个数称为图G的竞争数,记作k(G).一般来说计算图的竞争数是比较困难的,并且通过计算图的竞争数来刻画图已成为研究竞争图理论的一个重要内容.广义Halin图包括一个树的平面嵌入和一个连接树的叶子的圈.针对广义Halin图进行研究,确定了广义Halin图的竞争数.     

k-割宽临界树的一些构造方法(k≥3)

起源于超大规模集成电路设计和网络通讯的图的割宽（cutwidth）问题,就是把一个含有n个顶点的图G的全部顶点分别安装在一条直线的不同的整数点上,使得跨越各顶点的边数的最大值（即稠密度）达到最小.文章得到了κ–割宽临界树的一些构造方法（κ≥3）.     

一类距离图的圆色数

圆色数是图的一个重要参数 .距离图G(Z ,D)是具有顶点集Z ={ 0 ,± 1,± 2 ,… }、距离集D ,且满足顶点x与y相邻的充要条件是y -x∈D的无限图 .本文确定了两类距离图G(Z ,Dm ,k ,k + 1)和G(Z ,Dm ,k ,k + 1.k + 2 )的圆色数 .     

2006年贵州省中学生数学竞赛试卷

一、选择题(共4小题,每小题6分,满分24分)图11.数学中,为了简便,记1 2 3 … (n-1) n=Σni=1i,1×2×3×…×(n-1)×n=n!,那么2006!2005! Σ2005i=1i-Σ2006i=1i的值是()。A、0;B、1;C、2005;D、2006.2.如图1,一枚棋子放在七边形ABCDEFG的顶点A处,现顺时针方向移动这枚棋子10次,移动规则是:第K次依次移动K个顶点,如第一次移动1个顶点,棋子停在顶点B处,第二次移动2个顶点,棋子停在顶点D处,依这样的规则,在这10次移动的过程中,棋子不可能停到的顶点是()。A·C,E,F;B·C,E,G;C·G,E;D·E,F.3.已知一列数a1,a2,a3,…,an中,a1=0,a2=2a…     

对杨辉三角的一条性质的引申

杨辉三角有许多精美的性质，其中有一条为：以杨辉三角每个数为顶点（下面把每个顶点的数叫做杨辉码），从每个顶点向他的下层最接近的两个顶点画两条有向边，构成一个“杨辉图”（见图1），则每个顶点上的杨辉码恰为从根到此顶点的有向路经的条数．     

关于图的瑕边着色

图G=(V,E)的一个(λ,β)-瑕k-边着色是一个从E到{1,2,…,k}的映射,且存在一个最小整数β≥1,对每一个色j∈{1,2,…,β},至少存在一个顶点uj∈V(G)使得顶点uj关联着有色的j条边;对每一个色l∈{β+1,…,k},没有两条相邻边着有色l.图G的(λ,β)-瑕色数被表示为χ(λ,β)(G),它是一个最小的整数,使对整数k≥χ(λ,(β)G),图G总有一个(λ,β)-瑕k-边着色.在这篇文章中,我们证得χ(λ,1)(G)+λ-1≤χ′(G)≤χ(λ,1)(G)+,其中χ′(G)是G的正常边色数,并确定了几个特殊图类的瑕色数.     

图的色多项式问题

定义1 设图G为含有P个顶点的标定图,对其进行X—正常染色的方法数是X的一个函数,可表示成X的一个多项式,称为图G的色多项式,记为f(G,X)。 引理1 给定图G,设u、v∈V(G),e=(u,v)∈E(G)     

圈长为3的k圈图laplacian矩阵谱的界

设G为n阶的连通k(k 3)圈图,λ1(G)是图G的laplacian矩阵的最大特征值.本文讨论了圈长为3的k圈图的最大特征值与其顶点数及各顶点的悬挂边个数之间的关系.     

图的圆色数的一些结果

设k和d是2个互素的正整数且k≥2d．G^dk是一个图,它的顶点集合为{0,1,…,k-1},边集合为{ij｜d≤｜i-j｜≤k-d,i,j=0,1,…,k-1}．图G的圆色数χc（G）定义为使得图G与G^dk同态的2个正整数k和d的最小比值k／d．研究了χc（G）和χc（G-v）之间的关系,对任意顶点v求出了χc（G^dk-v）的精确值,给出了具有对任意顶点χc（G-v）=χc（G）-1和其他特定性质的图类;并对图的圆色数的一些下界进行了探讨,给出了图的圆色数达到下界χc-1＋1／d的充要条件,这里χ和α分别是图G的点色数和独立数．     

不含3-圈和4-圈的平面图的列表均匀染色

任意给定图G的一个k-一致列表L,若G是L-可染的,且满足每种颜色至多在「｜V（G）/k｜」个点上出现,则称G是k-均匀可选择的．若图G有一个正常k-顶点染色满足任两个色类中的顶点数至多相差1,则称G是k-均匀可染的．应用discharge方法讨论了不含3-圈和4-圈的平面图的结构,证明了对于不含3-圈和4-圈的平面图G,当k≥{max△（G）,6）时,G是k-均匀可选择的,同时G也是k-均匀可染的．     

两个图的冠的秩

设G_1和G_2分别是n阶与m阶顶点互不相邻的简单图,G_1G_2称为G_1与G_2的冠,是通过将G_2复制n个后,把G_1的第i-个顶点与G2的第i-复制的每一个顶点相连而得到的图。本文讨论了一些特殊图类的冠的邻接矩阵的秩,主要是当G2为完全图,完全二部图,Petersens图和CP(k)时两个图的冠。     

几类GwPm图的色唯一性

设w∈V(G),用GwPm表示把Pm的一个端点和w重迭得到的图.Gn,Hn分别表示图G的顶点v,H的顶点w和Kn的一个点重迭所得到的图.如果h(G)=h(H),且h(G-v)=h(H-w),则(1)h(GvPm)=h(HwPm),(2)h(Gn)=h(Hn).并用这个结果证明了几类GwPm图补图的色唯一性.     

一种带有限制的缺陷染色的研究

设G是一个图.如果图G的顶点能够用k个颜色来染,通过这种染色使得它的每个顶点至多有d个染相同颜色的顶点和它相邻,而且这样的顶点最少为t个,那么我们称图G是(k,d,t)*-可染的.在这个新定义的基础上,本文主要给出了几种特殊图类的一些结果和它们的证明,诸如圈、完全图等.另外,通过带有限制的缺陷染色这个新定义提出了对平面图四色问题的一点新看法,对四色定理的证明可能会有所帮助.     

M(P_n)和M(C_n)的邻点可区别均匀全染色

如果图G的一个正常全染色满足任意两相邻顶点的色集不同,并且任意两种颜色所染元素数目相差不超过1,则称为图G的邻点可区别均匀全染色,其所用最少染色数称为图G的邻点可区别均匀全色数.本文根据图的结构关系,运用构造法确定了路和圈的Mycielski图的邻点可区别均匀全色数.由此验证了邻点可区别均匀全染色的猜想对于路和圈的Mycielski图也是正确的.     

关于整和图的几个新结果

若图G的顶点可以用一个关于不同整数的标号函数f给出,使得对于G的任意两个不同的顶点u 和v,uv 是G 的边当且仅当f(u) + f(v) =f(w),w为G 的某个顶点,则图G称为整和图(integral sum graph).现给出完全三部图K1,1,r r≥3的(整)和数、完全三部图K1,r,r r≥2(整)和数的一个上下界,并证明了扇图 Fn 及任意个扇图在中心处相交构成的图是整和图,同时得到荷兰风车Dn 也是整和图.     

爱因斯坦做过的题目

爱因斯坦是著名的物理学家,有关他的故事很多,下面是爱因斯坦做过的一个填数问题。把九个数1、2、3、…、8、9填进图1中的九个圆圈,使图中七个三角形顶点上的三个数之和都相等。     

第十四届全俄中学生数学奥林匹克试题及解答

八年级1.在正八边形的顶点上,是否可以记上数1,2,…,8,使得任意三个相邻的顶点上的数之和为:(1)大于11,(2)大于13?解(1)可以的.图1就是满足条件的一个例子。