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.     

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     

关于3连通图的容错直径和宽直径

容错直径和宽直径是度量网络可靠性和有效性的重要参数．对任意k连通图，它的容错直径Dk不超过宽直径dk,本证明：当D2=2时，d3≤max{D， l，2D3-2}；当D2≥3时，d3≤(D2-1)[2(D2-1)(D3-1)-D2-2] 1．     

广义Petersen图的宽直径

Generalized Petersen graphs are commonly used interconnection networks,and wide diameter is an important parameter to measure fault-tolerance and efficiency of parallel pro- cessing computer networks.In this paper,we show that the diameter and 3-wide diameter of generalized Petersen graph P (m,a) are both O( m 2a ),where a ≥ 3.     

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

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.     

关于图的直径和平均距离

图的直径和平均距离是度量网络有效性的两个重要参数．Ore通过图的顶点数和直径给出无向图的最大边数．Entringer，Jakson，Slater和Ng，Teh通过图的顶点数和边数分别给出无向图和有向图平均距离的下界．该文提供这两个结果的简单证明，给出有向图类似Ore的结果，并通过图的直径改进Entringer等人的结果到更一般的情形．结合本文和Ore的结果，可以得到一个无向图和有向图平均距离的下界，它比Plesnik得到的下界更好．     

直径为三的不可上嵌入的图

本文证明了只存在一类3-边连通的直径为三的12个点的不可上嵌入的图.     

直径为4的图的最大亏格

本文证明了如下结果:设G是直径为4的简单囹,若G不含3阶完全子图K3,则G的Betti亏数ξ(G)≤2,因此有G的最大亏格γM(G)≥1/2β(G)-1.而且,在这种意义下,所得到的界是最好的.     

Total Domination in Graphs with Diameter 2

The total domination number of a graph G is the minimum cardinality of a set S of vertices, so that every vertex of G is adjacent to a vertex in S. In this article, we determine an optimal upper bound on the total domination number of a graph with diameter 2. We show that for every graph G on n vertices with diameter 2, . This bound is optimal in the sense that given any , there exist graphs G with diameter 2 of all sufficiently large even orders n such that .     

Classification of Regular Planar Graphs with Diameter Two

In the present paper, the regular planar graphs with diameter two are classified.     

Cayley Graphs of Diameter Two from Difference Sets

Let and be the largest order of a Cayley graph and a Cayley graph based on an abelian group, respectively, of degree d and diameter k. When , it is well known that with equality if and only if the graph is a Moore graph. In the abelian case, we have . The best currently lower bound on is for all sufficiently large d. In this article, we consider the construction of large graphs of diameter 2 using generalized difference sets. We show that for sufficiently large d and if , and m is odd.     

Nonexistence of some Antipodal Distance-regular Graphs of Diameter Four

We find an inequality involving the eigenvalues of a regular graph; equality holds if and only if the graph is strongly regular. We apply this inequality to the first subconstituents of a distance-regular graph and obtain a simple proof of the fundamental bound for distance-regular graphs, discovered by Juri i , Koolen and Terwilliger. Using this we show that for distance-regular graphs with certain intersection arrays, the first subconstituent graphs are strongly regular. From these results we prove the nonexistence of distance-regular graphs associated to 20 feasible intersection arrays from the book Distance-Regular Graphs by Brouwer, Cohen and Neumaier .     

直径为4的树的IC-着色和IC-指数

根据Salehi等人在Discrete Mathematics上提出的图的IC-指数及极大IC-着色的相关概念,研究了直径为4的树T=T(m_1,m_2,…,m_s)的IC=着色问题·得到了当2≤<_1,m_2,…,m_s-1≤m_s,s≥2时,树T的IC-指数为Π_j=1~s(2~mj+1)+(2m,+1),其极大IC-着色有|π|种,其中|π|为m_1,同_2,…m_…s-1的全排列数.这为确定图的IC-指数提供了一般方法.     

关于直径为４的图的最大亏格

该文证明了如下结果：设犌为直径为４的简单图,若犌不含３阶完全子图犓３,则犌的Ｂｅｔｔｉ亏数ξ（犌）≤４,因此有犌的最大亏格γ犕（犌）≥ １２β（犌）－２．     

一类3-连通图的上可嵌入性

结合图的k-边形2-因子条件，确定了一类上可嵌入的3-连通图。     

A Characterization of Distance-Regular Graphs with Diameter Three

We characterize the distance-regular graphs with diameter three by giving an expression for the number of vertices at distance two from each given vertex, in terms of the spectrum of the graph.