完全$r$部图乘积上的Graham猜想

图G的Pebbling数f(G)是最小的正整数n,使得不论n个Pebble如何放置在G的顶点上,总可以通过一系列的Pebbling移动把1个Pebble移到任意一点上,其中Pebbling移动是从一个顶点处移走两个Pebble而把其中一个移到与其相邻的一个顶点上.Graham猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H).本文证明对于一个完全γ部图和一个具有2-Pebbleing性质的图来说,Graham猜想成立.作为一个推论,当G和H均为完全γ部图时,Graham猜想成立.     

完全r部图乘积上的Graham猜想

图G的Pebbling数f(G)是最小的正整数n,使得不论n个Pebble如何放置在G的顶点上,总可以通过一系列的Pebbling移动把1个Pebble移到任意一点上,其中Pebbling移动是从一个顶点处移走两个Pebble而把其中一个移到与其相邻的一个顶点上。Graham猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H)。本文证明对于一个完全r部图和一个具有2-Pebbleing性质的图来说,Graham猜想成立。作为一个推论,当G和H均为完全r部图时,Graham猜想成立。     

几类二部图的pebbling数

Chung定义了图G上的一个pebbling移动是从一个顶点移走两个pebble而把其中的一个移到与其相邻的一个顶点上.连通图G的pebbling数f(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到G的任意一个顶点上.Graham猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H).作者们验证了三类二部图的2-pebbling性质以及当H为此类二部图,G为一个2-pebbling性质的图时,Graham猜想成立.     

广义友谊图乘积上的Graham pebbling猜想

连通图G的pebbling数f(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到图G的任意一个顶点上.Graham猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H).文中证明了当H为友谊图或广义友谊图,G是一个具有2-pebbling性质的图时,Graham猜想成立.作为一个推论,文中也证明了当G和H是友谊图或广义友谊图时,Graham猜想成立.     

圈的中间图pebbling数和Graham猜想

图G的一个pebbling移动是从一个顶点移走2个pebble, 而把其中的1个pebble移到与其相邻的一个顶点上. 图G 的pebbling数f(G)是最小的正整数n, 使得不论n个pebble 如何放置在G的顶点上, 总可以通过一系列的pebbling移动, 把1个pebble移到图G的任意一个顶点上. 图G 的中间图M(G) 就是在G 的每一条边上插入一个新点, 再把G 上相邻边上的新点用一条边连接起来的图. 对于任意两个连通图G和H, Graham猜测f(G\times H)\leq f(G)f(H). 首先研究了圈的中间图的pebbling 数, 然后讨论了一些圈的中间图满足Graham猜想.     

完全二部图乘积上的 Graham pebbling猜想

图G的pebbling数f(G)是最小的整数n,使得不论n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把1个pebble移到任意一个顶点上,其中的pebbling移动是从一个顶点处移走两个pebble而把其中的一个移到与其相邻的一个顶点上. Graham猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H).证明了对于一个完全二部图和一个具有2-pebbling性质的图来说,Graham猜想是成立的,作为一个推论,当G和H都是完全二部图时,Graham猜想成立.     

多扇图的Pebbling数和Graham猜想

图G的pebbling数f(G)是最小的整数n,使得不论n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把1个pebble移到任意一个顶点上,其中一个pebbling移动是从一个顶点处移走两个pebble而把其中的一个移到与其相邻的一个顶点上。Graham猜想对于任意的连通图G和H有f(G×H)f(G)f(H)。多扇图F_n1,n2,…,nm是指阶为n₁+n₂+…+n_m+1的联图P₁∨(P_n1∪P_n2∪…∪P_nm)。本文首先给出了多扇图的pebbling数,然后证明了多扇图F_n1,n2,…,nm具有2-pebbling性质,最后论述了对于一个多扇图和一个具有2-pebbling性质的图的乘积来说,Graham猜想是成立的。作为一个推论,当G和H都是多扇图时,Graham猜想成立。     

几类图的pebbling数

金芳蓉定义了图 G上的一个 pebbling 移动是从一个顶点处移走两个pebble 而把其中的一个移到与其相邻的一个顶点上. 图G的pebbling数f(G)是最小的整数n, 使得不管n 个pebble 如何放置在G的顶点上, 总可以通过一系列的 pebbling 移动把一个pebble 移到 G的任一个顶点上. Graham 猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H). 计算了两个扇图的积和两个轮图的积的pebbling数, 作为推论, 当G和H同时是扇图或轮图时, Graham 猜想成立.     

星形图乘积的pebbling数

图 G的 pebbling数 f(G)是最小的整数 n,使得不论 n个 pebble如何放置在 G的顶点上 ,总可以通过一系列的 pebbling移动把一个 pebble移到任意一个顶点上 ,其中的 pebbling移动是从一个顶点上移走两个 pebble而把其中的一个移到与其相邻的一个顶点上 .设 K1,n为 n+1个顶点的星形图 .本文证明了 (n+2 )(m+2 )≥ f K1,n× K1,m)≥ (n+1) (m+1) +7,n>1,m>1.     

图中具有正交（g,f）因子分解的子图

设G是一个 (mg +k ,mf -k) -图 (1≤k 相似文献   

关于图中子图的（n,k）—正交因子分解

设G是一个具有顶点集V(G)和边集E(G)的图. 设g和f是定义在V(G)上的两个整数值函数,使得g(x)f(x)对所有的点x∈V(G)都成立.如果G是一个(mg+n,mf-n)-图,1n<m2k,且g(x)2k-1对所有的点x∈V(G)都成立,则对任意给定具有|E(H)|=nk边的G的子图H,存在G的一个子图G′使G′有一个(g,f)-因子分解(n,k)-正交H.     

平面图最小平衡二部划分的上界

关于平面图的平衡二部子图的研究有一个猜想:任意一n个顶点的平面图G(V,E),必含有一个平衡二部子图G(V_1,V_2)使得e(V_1,V_2)≤n.证明了若n个顶点的哈密尔顿平面图G(V,E)中含有一个近似等边三角形,n≥18,那么G(V,E)必含有一个平衡二部子图G(V_1,V_2)使得e(V_1,V_2)≤n.     

(a,b,n)-临界图的几个充分条件

设G是一个图 .设g和f是两个定义在V(G)上的整值函数使得对V(G)所有顶点x有g(x) ≤f(x) .图G被称为 (g ,f,n) 临界图 ,如果删去G的任意n个顶点后的子图都含有G的 (g ,f) 因子 .本文给出了图是 (a ,b ,n) 临界图几个充分条件 ,即度和邻域条件 .进一步指出这些条件是最佳的 .     

关于图是(g,f,n)-临界图的充分条件

设G是一个图. 设g和f是两个定义在V(G)上的整值函数使得对V(G)所有的顶点x有g(x)f(x). 图G被称为(g,f,n)-临界图,如果删去G的任意n个顶点后的子图都含有G的(g,f)-因子. 本文给出了图是(a,b,n)-临界图几个充分条件. 进一步指出这些条件是最佳的. 例如,如果对V(G)所有的顶点x和y都有g(x)＜f(x), n+g(x)dG(x)和g(x)/(dG(x)-n)f(y)/dG(y),则G是(g,f,n)-临界图.     

L4(4)的非交换图刻画

令G是一个有限非交换群.如下定义群G的非交换图▽(G):其顶点集是G\Z(G),任意两个顶点x和y相连的充要条件是[x,y]≠1.2006年, Abdollahi A.,Akbari S.和Maimani H.R.提出了如下猜想:若群G满足条件▽(G)≌▽(M),其中M是有限非交换单群,则G≌M.尽管该猜想对于具有非连通素图的有限单群以及交错群A10足成立的,但是人们仍不知道它对于除A10外的具有连通素图的有限单群是否成立.该文证明了上述猜想对于射影特殊线性单群L4(4)也是成立的.     

分数(g,f,m)-消去图的不相邻顶点领域并条件（英文）

一个图称为分数(g,f,m)-消去图若删除任意m条边后的剩余子图依然存在分数(g,f)-因子.本文证明若图G的阶为n,1≤a≤g(x)≤f(x)-Δ≤b-Δ对任意顶点x∈V(G)成立,δ(G)≥(b-Δ)(b+1)/a+2m,n≥(a+b)(2(a+b)+2m-1)/(a+Δ),且|N_G(x_1)∪N_G(x_2)|≥(b-Δ)n/(a+b),对任意不相邻顶点x_1和x_2都成立,则G是分数(g,f,m)-消去图.这个领域并条件在一定程度上是最好的.     

边着色路到完全图的嵌入

一、一个猜想设 P_n 为具有 n 个顶点的一条路,它的 n-1条边着上了不同的颜色,若这个着色能扩充为 n 个顶点的完全图 K_n 的一个正常的 x′(K_n)一边着色,则称边着色路 P_n 能嵌入于完全图.一般说来,设 G 是具有边色数 x′(G)的一个简单图,令 M(G)为 G 中所有满足以下性质的子图 H(?)G 的集合:存在 G 的一种正常的 x′(G)-边着色使得 H 的各条边具有不同的颜色.设 K_n 是 n 个顶点的完全图,把集合 M(K_n)简记为 M_n 于是我们一开始提出的问题“P_n 能否嵌入于完全图”等价于“P_n 是否属于 M_n”.     

循环分布图最大边数猜想的一个反例

令f(n)为恰有n个顶点，任意两个循环长度都不相等的图的最多边数．1975年，Erdos提出确定f(n)的问题(见[1]P274，Problem11)．1986年．Y．Shi证明了对任意自然数．≥3，有f(n)≥n [(√8n-23 1／1)／2]，且当3≤n≤17时．等号成立．进而猜想：对于任何自然数n≥3，上述等式都成立．本文对该猜想给出一个反例。     

关于图的减控制与符号控制

给定一个图G=(V,E),一个函数f:V→{-1,0,1}被称为G的减控制函数,如果对任意v∈V(G)均有∑_μ∈N[v]f(μ)≥1。G的减控制数定义为γ^-(G)=min{∑_v∈Vf(v)|f是G的减控制函数}。图G的符号控制函数的正如减控制函数,差别是广{-1,0,1}换成{-1,1}。符号控制数γ_s(G)是类似的。本文获得γ^-G)和γ_s(G)的一些下界。同时也证明并推广了 Jean Dunbar等提出的一个猜想,即对任意 n阶 2部图 G,均有γ^-(G)≥ 4(n+1^1/2-1)-n成立。     

关于图的符号星控制数

设G=(V,E)是一个图,u∈V,则E(u)表示u点所关联的边集.一个函数f:E→{-1,1}如果满足■f(e)≥1对任意v∈V成立,则称f为图G的一个符号星控制函数,图G的符号星控制数定义为γ'_(ss)(G)=min{■f(e):f为图G的一个符号星控制函数}.给出了几类特殊图的符号星控制数,主要包含完全图,正则偶图和完全二部图.