路和圈的最优一般Pebbling数

图G的一个一般pebbling移动是从一个顶点移走p(p≥2)个pebble,而把其中的一个移到与其相邻的一个顶点上.图G的一般pebbling数fgl(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列一般pebbling移动把一个pebble移到图G的任意一个顶点上.图G的一个分布是可解的,当通过一系列一般pebbling移动,能把一个pebble移到其任意一个顶点上.图G的最优一般pebbling数fgl’(G)是可解分布中最小的,即利用fgl’(G)个pebble以构造一个可解分布,且这时需要的pebble个数最少.本文采用反证法,通过去掉一个顶点,改变路(或圈)为其子图,并选择一个可解分布.而这时所用的pebble数要比其最优一般pebbling数小,得到矛盾,这样就证明了路和圈的最优一般pebbling数.     

轮图中间图的pebbling数

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

关于给定偶图的圈长分布的计算

阶为υ的图G的圈长分布是序列（c1,c2,…，cυ），其中 是G中长为i的圈的数目，得到了计算给定简单偶图G的图长分布的公式。     

几类图的pebbling数

图G的pebbling数 f （G ）是最小的整数n ,使得不论n个pebbles如何放置在图G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到任意一个顶点上,其中一个pebbling移动是从一个顶点处移走两个pebbles,而把其中的一个移到与其相邻的一个顶点上。文章给出图Fn？Pk、Wn？Pk和双轮图Wm？Pk-1？Wn的peb？bling数。     

点泛圈偶图

设Ｇ是连通偶图，（Ｘ１，Ｘ２）是其顶点的二分类，｜Ｘ１｜＝｜Ｘ２｜＝ｎ，δ（Ｇ）≥ｔ≥３，且对于Ｘｉ中的任意两点ｕ和ｖ，均有｜Ｎ（ｕ）∪Ｎ（ｖ）｜≥ｎ－（ｔ－２），ｉ＝１，２，文中对ｔ≤６的情况，证明Ｇ是点泛圈偶图。     

关于唯一r-偶泛圈图

设r≥4且r是偶整数．阶为2n的偶图G被称为唯一r-偶泛圈图，如果对每个偶整数t，r≤t≤2n，G恰含一个长为t的圈，且G不含长小于，的圈．若G是唯一r-偶泛圈圈，则称G是r-UB-图．证明了恰好存在6个外可平面的r-UB-图和对m≤3恰好存在12个阶为2n和边数为2n＋m的r－UB－图．     

路和圈并图的算术标号

证明了Ｐｎ１∪Ｐｎ２∪…∪Ｐｎｋ及Ｃｎ∪Ｃｍ∪（ｎ≡１（ｍｏｄ２）,ｍ≡４（ｍｏｄ４））是算术图 。     

由圈长分布确定的偶图

阶为n的图G的圈长分布是序列(c1，c2，…，cn)，其中ci是图G中长为i的圈数，作者得到如下结果：设n≤r≤min{n 6，2n-3}，则Kn,r是由它的圈长分布确定的。     

圈与完全偶图的笛卡尔乘积的联结数

本文给出了圈与完全偶图的笛卡尔乘积的联结数计算公式,证明了如下定理:这里S≥3,m≥2,n≥2,l=min{m,n},均为整数.     

唯一偶泛圈图的一个定理

设G是一个偶图,u是偶数且是G的阶,若对每个偶数t,4≤t≤v,G恰有一个长为t的圈,则称G是唯一偶泛圈图（简称UB－图）。作者证明恰有6个v 4条边的UB－图。     

偶圈的Turán数和Wenger图

设G是一个图,G的Tur(a)n数记作ex(n;G),是指阶数为n的不含G作为子图的图的最大边数.根据Erd(o)s在1965年给出的偶圈C2m的Tur(a)n数ex(n;C2m)的上界10mn1+1/m和Wenger在1991年构造的偶图Hm(q),并由这种图得到的ex(n;C2m)(m=2,3,5)的下界cn1+1/m(其中c为一个与n无关的常数),可以知道,当n→+∞时,ex(n;C2m)=O(n1+1/m)(m=2,3,5).n1+1/m就是ex(n;C2m)的准确阶.给出了Wenger图Hm(q)的一些一般性质,并分别构造了Hm(q)中长为8的圈(m≥4)和Hm(q)中长为12的圈(m≥6), 从而证明了不可能由图Hm(q)得到ex(n;C2m)的所有准确阶.     

路和圈的广义Mycielski图的星色数

简单图的星染色是图的染色理论中的一个重要问题.为了深入研究图的星色数,我们用结构图论的方法,给出了路和圈的广义Mycielski图的星染色方法,得到了路和圈的广义Mycielski图的星色数.     

偶圈的Tur(a)n数和Wenger图

设G是一个图，G的Turan数记作ex（n；G），是指阶数为n的不含G作为子图的图的最大边数．根据Erdos在1965年给出的偶圈C2m的Turan数ex（n；C2m）的上界10mn^1＋1/m和Wenger在1991年构造的偶图Hm（q），并由这种图得到的ex（n；C2m）（m=2，3，5）的下界cn^1＋1/m（其中c为一个与n无关的常数），可以知道，当n→＋∞时，ex（n；C2m）=O（n^1＋1/m）（m=2，3，5）．n^1＋1/m就是ex（n；C2m）的准确阶．给出了Wenger图Hm（q）的一些一般性质，并分别构造了Hm（q）中长为8的圈（m≥4）和Hm（q）中长为12的圈（m≥6），从而证明了不可能由图Hm（q）得到ex（n；C2m）的所有准确阶．     

图的圈和路剖分

设G是一个顶点数为n的图,k为任意正整数且k≤n．Hikoe Enomoto和李浩证明了：如果一对不相邻顶点的度和至少为n-k 1,其中k≤n，则除了k=2，G=G5,G能被剖分成k个子图Hi，l≤i≤k，其中Hi是圈或K1或K2．本文中证明了任何一对不相邻顶点的度和至少为n-k，则G能被剖分成k个子图Ki,l≤i≤k，其中Hi是圈或是路．     

定向图中长的路和回路

本文对定向图中存在长不小于给定值的路和回路给出了关于次的几个充分条件。     

Δ-free图的最长路和最长圈

得到Δ-free图的最长路和最长圈的下界为2δ＋2,以及存在Hamilton圈的一个充分条件δ≥max{ ,α},δ是图G的顶点的最小度,α是G的独立数p＝ V(G) ≥15．     

路与圈的叉积图的消圈数

研究了路与圈的叉积图的消圈数.对一般的路Pm和圈Cn,得到了Pm×Cn的消圈数的一个紧的下界;对一些特殊的Pm路和圈Cn,得到Pm×Cn的消圈数的准确值.     

路与圈的笛卡尔乘积图的消圈数

探讨路与圈的笛卡尔乘积图的消圈问题,对一般的路与圈,根据引理1及推论1推导出它们的笛卡尔乘积图的消圈数的一个紧的下界;进而对一些特殊的路与圈,推导出它们的笛卡尔乘积图的消圈数的准确值.