圈的中间图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移动把一个pebble移到图G的任意一个顶点上.Graham猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H).文中证明了当H为友谊图或广义友谊图,G是一个具有2-pebbling性质的图时,Graham猜想成立.作为一个推论,文中也证明了当G和H是友谊图或广义友谊图时,Graham猜想成立.     

完全γ部图乘积上的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猜想成立。     

完全$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猜想成立.     

图的中间图2-pebbling性质和Graham猜想（英文）

本文研究了图的2-pebbling性质和Graham猜想.利用图的pebbling数的一些结果,我们研究了路和圈的中间图具有2-pebbling性质,从而也证明了路的中间图满足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猜想成立。     

完全二部图乘积上的 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数

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猜想成立.     

算术图一个猜想的证明

Ａｃｈａｒｙａ和Ｈｅｄｇｅ提出猜想：(i)若圈Ｃ_4t＋１( t≥1, t∈N) 是(k, d )－算术图，则Ｋ＝２ｄｔ+ 2r ( r≥0, r∈N ) ; ( ii) 若圈C_4t＋3是(k, d )-算术图, 则k= (2t+ 1) d + 2r ( r≥0, r∈N ). 本文证明了上述猜想为真.     

关于Mycielski图循环色数的猜想

通过引进Mycielski图点集的一类特殊划分,利用该划分在Mycielski图循环着色中的特点改进了如下猜想:完全图的Mycielski图的循环色数等于它的点色数.     

关于商高数的Jemanowicz猜想

本文研究了商高数的Jemanowicz猜想的整数解问题.利用初等数论方法,获得了该猜想的两个新结果并给出证明,推广了文献[4–8]的结果.     

图的关联色数和关联着色猜想

本文综述了图的关联着色的已有结果，证明了关联着色猜想对于完全3—部图和高度留成立，确定了路、圈、扇、轮和加边轮等特殊图类的关联色数．     

关于偶正则图的R2边连通度的某些结果

Let G be a connected k(≥3)-regular graph with girth g. A set S of the edges in G is called an R2-edge-cut if G-S is disconnected and contains neither an isolated vertex nor a one-degree vertex. The R2-edge-connectivity of G, denoted by λ″(G), is the minimum cardinality over all R2-edge-cuts, which is an important measure for fault-tolerance of computer interconnection networks. In this paper, λ″(G)=g(2k-2) for any 2k-regular connected graph G(≠K5) that is either edge-transitive or vertex-transitive and g≥5 is given.     

单形中面的性质及其应用

本文首先给出单形中面的概念，得到了单形中面的一些性质，作为其应用，建立了涉及单形中面的两个不等式。     

平面图3色可染的一个充分条件

Steinberg猜想既没有4-圈又没有5-圈的平面图是3色可染的. Xu, Borodin等人各自独立地证明了既没有相邻三角形又没有5-和7-圈的平面图是3 色可染的. 作为这一结果的推论, 没有4-, 5-和7-圈的平面图是3色可染的. 本文证明一个比此推论更接近Steinberg猜想的结果, 设G是一个既没有4-圈又没有5-圈的平面图, 若对每一个k∈{3, 6, 7}, G都不含(k, 7)-弦, 则G是3色可染的, 这里的(k, 7)-弦是指长度为7+k-2的圈的一条弦, 它的两个端点将圈分成两条路, 一条路的长度为6, 另一条路的长度为k-1.     

关于Je(s)manowicz猜想的一个注记

本文研究了Je(s)manowicz于1956年提出的关于丢番图方程(1.1)解的猜想.利用数论中的一些方法,得到了丢番图方程(1.2)的所有正整数解,证明了Je(s)manowicz猜想在这类情况下的正确性.     

ON A PAIR OF NON-ISOMETRIC ISOSPECTRAL DOMAINS WITH FRACTAL BOUNDARIES AND THE WEYL-BERRY CONJECTURE

ＯＮＡＰＡＩＲＯＦＮＯＮＩＳＯＭＥＴＲＩＣＩＳＯＳＰＥＣＴＲＡＬＤＯＭＡＩＮＳＷＩＴＨＦＲＡＣＴＡＬＢＯＵＮＤＡＲＩＥＳＡＮＤＴＨＥＷＥＹＬＢＥＲＲＹＣＯＮＪＥＣＴＵＲＥＳＬＥＥＭＡＮ，Ｂ．Ｄ．ＣＨＥＮＨＵＡＭａｎｕｓｃｒｉｐｔｒｅｃ...     

对称本原图的集指数与本原简单图的广义上指数的极图

一个有向图D称为本原的，如果存在某个正整数k，使得对于D中的任一点x到任一点y都有长为k的途径，这样的正整数k中的最小者称为D的本原指数，作为本原指数概念的推广，R．A．Brualdi和柳柏濂于1990年引入了本原有向图的广义本原指数的新概念，本文给出了对称本原图的集指数的一些性质，并对本原简单图的广义上指数的极图进行了完全刻划。     

图与其补图谱半径之间的关系

本文我们将图与其补图结合起来，给出了图与其补图的谱半径所必须满足的两个不等式。