English

运筹学学报 ›› 2013, Vol. 17 ›› Issue (3): 35-44.

• 运筹学 • 上一篇    下一篇

圈的中间图pebbling数和Graham猜想

叶永升1,*, 刘芳1, 翟明清2   

  1. 1. 淮北师范大学数学科学学院，安徽淮北 235000 2. 滁州学院数学系, 安徽滁州 239012
  • 出版日期:2013-09-15 发布日期:2013-09-15
  • 通讯作者: 叶永升 E-mail:yeysh66@sina.com
  • 基金资助:

    国家自然科学基金(No.10971248), 安徽省科技厅自然科学基金(No.1208085QF119), 安徽省教育厅自然科学基金(Nos. KJ2013Z279, KJ2011B152, KJ2012B166, 2011SQRL070)

Pebbling numbers of middle graphs of cycles and Graham's conjecture

YE Yongsheng1,*, LIU Fang1, ZHAI Mingqing2   

  1. 1. School of Mathematical Sciences, Huaibei Normal University, Huaibei 235000, Anhui, China 2. Department of Mathematics, Chuzhou University, Chuzhou 239012, Anhui, China
  • Online:2013-09-15 Published:2013-09-15

PDF

779

被引次数

3

摘要： 图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数

Abstract:   A pebbling move on a graph G consists of taking two pebbles off one vertex and placing  one pebble on an adjacent vertex. The pebbling number of a connected graph G, denoted by f(G), is the least n such that any distribution of n pebbles on G allows one pebble to be moved to any specified, but arbitrary vertex by a sequence of pebbling moves. The middle graph M(G) of a graph G is the graph obtained from G by inserting a new vertex into every edge of G and by joining by edges those pairs of these new vertices which lie on adjacent edges of G. For any connected graphs G and H, Graham conjectured that  f(G\times H)\leq f(G)f(H). In this paper, we show  the pebbling numbers of  middle graphs of  cycles, and discuss that Graham^,s conjecture holds for  middle  graphs of some cycles.

Key words: Graham's conjecture, cycles, middle graphs, pebbling number

中图分类号: