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

• 作者: 冯荣权 金珠英
• 来源期刊: 中国科学A辑
• 关键词: pebbling Graham猜想 Descartes积 完全二部图
• 年，卷（期）: 2001,（3）
• 页码范围: 199-203
• 页数: 5页
• 字数: 4823字
• 语种: 中文
• DOI: 10.3321/j.issn:1006-9232.2001.03.002

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	冯荣权	北京大学数学科学学院	14	95	4.0	9.0