Maximum pebbling number of graphs of diameter three

Given a configuration of pebbles on the vertices of a graph G, a pebbling move consists of taking two pebbles off some vertex v and putting one of them back on a vertex adjacent to v. A graph is called pebbleable if for each vertex v there is a sequence of pebbling moves that would place at least one pebble on v. The pebbling number of a graph G is the smallest integer m such that G is pebbleable for every configuration of m pebbles on G. We prove that the pebbling number of a graph of diameter 3 on n vertices is no more than (3/2)n + O(1), and, by explicit construction, that the bound is sharp. © 2006 Wiley Periodicals, Inc. J Graph Theory     

星形图乘积的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.     

Graph pegging numbers

In graph pegging, we view each vertex of a graph as a hole into which a peg can be placed, with checker-like “pegging moves” allowed. Motivated by well-studied questions in graph pebbling, we introduce two pegging quantities. The pegging number (respectively, the optimal pegging number) of a graph is the minimum number of pegs such that for every (respectively, some) distribution of that many pegs on the graph, any vertex can be reached by a sequence of pegging moves. We prove several basic properties of pegging and analyze the pegging number and optimal pegging number of several classes of graphs, including paths, cycles, products with complete graphs, hypercubes, and graphs of small diameter.     

多扇图的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 in diameter two graphs and products of paths

Results regarding the pebbling number of various graphs are presented. We say a graph is of Class 0 if its pebbling number equals the number of its vertices. For diameter d we conjecture that every graph of sufficient connectivity is of Class 0. We verify the conjecture for d = 2 by characterizing those diameter two graphs of Class 0, extending results of Pachter, Snevily and Voxman. In fact we use this characterization to show that almost all graphs have Class 0. We also present a technical correction to Chung's alternate proof of a number theoretic result of Lemke and Kleitman via pebbling. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 119–128, 1997     

圈的中间图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猜想成立.     

Pebbling Graphs of Fixed Diameter

Given a configuration of indistinguishable pebbles on the vertices of a connected graph G on n vertices, a pebbling move is defined as the removal of two pebbles from some vertex, and the placement of one pebble on an adjacent vertex. The m‐pebbling number of a graph G, , is the smallest integer k such that for each vertex v and each configuration of k pebbles on G there is a sequence of pebbling moves that places at least m pebbles on v. When , it is simply called the pebbling number of a graph. We prove that if G is a graph of diameter d and are integers, then , where denotes the size of the smallest distance k dominating set, that is the smallest subset of vertices such that every vertex is at most distance k from the set, and, . This generalizes the work of Chan and Godbole (Discrete Math 208 (2008), 15–23) who proved this formula for . As a corollary, we prove that . Furthermore, we prove that if d is odd, then , which in the case of answers for odd d, up to a constant additive factor, a question of Bukh (J Graph Theory 52 (2006), 353–357) about the best possible bound on the pebbling number of a graph with respect to its diameter.     

Rubbling and optimal rubbling of graphs

A pebbling move on a graph removes two pebbles at a vertex and adds one pebble at an adjacent vertex. Rubbling is a version of pebbling where an additional move is allowed. In this new move one pebble is removed at vertices v and w adjacent to a vertex u and an extra pebble is added at vertex u. A vertex is reachable from a pebble distribution if it is possible to move a pebble to that vertex using rubbling moves. The rubbling number of a graph is the smallest number m needed to guarantee that any vertex is reachable from any pebble distribution of m pebbles. The optimal rubbling number is the smallest number m needed to guarantee a pebble distribution of m pebbles from which any vertex is reachable. We determine the rubbling and optimal rubbling number of some families of graphs and we show that Graham’s conjecture does not hold for rubbling numbers.     

Doppelgangers and Lemke graphs

Let $G$ be a connected graph. A configuration of pebbles on $G$ is a function that assigns a nonnegative integer to each vertex. A pebbling move consists of removing two pebbles from one vertex and placing one pebble on an adjacent vertex. A configuration is solvable if after making pebbling moves any vertex can get at least one pebble. The pebbling number of $G$, denoted $\pi \left(G\right)$, is the smallest integer such that any configuration of $\pi \left(G\right)$ pebbles on $G$ is solvable. A graph has the two-pebbling property if after placing more than $2\pi \left(G\right)?q$ pebbles on $G$, where $q$ is the number of vertices with pebbles, there is a sequence of pebbling moves so that at least two pebbles can be placed on any vertex. A graph without the two-pebbling property is called a Lemke graph. Previously, an infinite family of Lemke graphs was shown to exist by subdividing edges of the original Lemke graph. In this paper, we introduce a new way to create infinite families of Lemke graphs based on adding vertices as well as subdividing edges. We also characterize the configurations that violate the two-pebbling property on these graphs and conjecture another infinite family of Lemke graphs that generalizes the original Lemke graph.     

Pebbling Graphs of Diameter Three and Four

Given a configuration of pebbles on the vertices of a connected graph G, a pebbling move is defined as the removal of two pebbles from some vertex and the placement of one of these on an adjacent vertex. The pebbling number of a graph G is the smallest integer k such that for each vertex v and each configuration of k pebbles on G there is a sequence of pebbling moves that places at least one pebble on v. We improve on a bound of Bukh by showing that the pebbling number of a graph of diameter three on n vertices is at most , and this bound is best possible. Further, we obtain an asymptotic bound of for the pebbling number of graphs of diameter four. Finally, we prove an asymptotic bound for pebbling graphs of arbitrary diameter, namely that the pebbling number for a diameter d graph on n vertices is at most , where is a constant depending upon d. This also improves another bound of Bukh.     

Threshold and complexity results for the cover pebbling game

Given a configuration of pebbles on the vertices of a graph, a pebbling move is defined by removing two pebbles from some vertex and placing one pebble on an adjacent vertex. The cover pebbling number of a graph, γ(G), is the smallest number of pebbles such that through a sequence of pebbling moves, a pebble can eventually be placed on every vertex simultaneously, no matter how the pebbles are initially distributed. We determine Bose-Einstein and Maxwell-Boltzmann cover pebbling thresholds for the complete graph. Also, we show that the cover pebbling decision problem is NP-complete.     

Graham's pebbling conjecture on products of cycles

Chung defined a pebbling move on a graph G to be the removal of two pebbles from one vertex and the addition of one pebble to an adjacent vertex. The pebbling number of a connected graph is the smallest number f(G) such that any distribution of f(G) pebbles on G allows one pebble to be moved to any specified, but arbitrary vertex by a sequence of pebbling moves. Graham conjectured that for any connected graphs G and H, f(G×H)≤ f(G)f(H). We prove Graham's conjecture when G is a cycle for a variety of graphs H, including all cycles. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 141–154, 2003     

Two-pebbling and odd-two-pebbling are not equivalent

Let $G$ be a connected graph. A configuration of pebbles assigns a nonnegative integer number of pebbles to each vertex of $G$. A move consists of removing two pebbles from one vertex and placing one pebble on an adjacent vertex. A configuration is solvable if any vertex can get at least one pebble through a sequence of moves. The pebbling number of $G$, denoted $\pi \left(G\right)$, is the smallest integer such that any configuration of $\pi \left(G\right)$ pebbles on $G$ is solvable. A graph has the two-pebbling property if after placing more than $2\pi \left(G\right)-q$ pebbles on $G$, where $q$ is the number of vertices with pebbles, there is a sequence of moves so that at least two pebbles can be placed on any vertex. A graph has the odd-two-pebbling property if after placing more than $2\pi \left(G\right)-r$ pebbles on $G$, where $r$ is the number of vertices with an odd number of pebbles, there is a sequence of moves so that at least two pebbles can be placed on any vertex. In this paper, we prove that the two-pebbling and odd-two-pebbling properties are not equivalent.     

Pebbling numbers of some graphs

Chung defined a pebbling move on a graphG as the removal of two pebbles from one vertex and the addition of one pebble to an adjacent vertex. The pebbling number of a connected graphG, f(G), is the leastn such that any distribution ofn pebbles onG allows one pebble to be moved to any specified but arbitrary vertex by a sequence of pebbling moves. Graham conjectured that for any connected graphsG andH, f(G xH) ≤ f(G)f(H). In the present paper the pebbling numbers of the product of two fan graphs and the product of two wheel graphs are computed. As a corollary, Graham’s conjecture holds whenG andH are fan graphs or wheel graphs.     

关于亲和数的一个注记

本文研究了一类整数序列(2n)2n 1的某些性质,利用费玛数和数论函数的某些性质,获得了验证此类整数是否是亲和数和完全数的方法,既不与其他正整数构成亲和数对也不是完全数.     

The Pseudoachromatic Number of a Graph

The pseudoachromatic number of a graph G is the maximum size of a vertex partition of G (where the sets of the partition may or may not be independent) such that, between any two distinct parts, there is at least one edge of G. This parameter is determined for graphs such as cycles, paths, wheels, certain complete multipartite graphs, and for other classes of graphs. Some open problems are raised.AMS Subject Classification (1991): primary 05C75 secondary 05C85