完全二部图乘积上的 Graham pebbling猜想 |
| |
作者姓名: | 冯荣权 金珠英 |
| |
作者单位: | (1)北京大学数学科学学院, 北京 100871 ,中国;(2)大邱天主教大学校数学科, 庆山713-702,韩国 |
| |
基金项目: | 国家自然科学基金资助项目(批准号:69873002,10001005) |
| |
摘 要: | 图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猜想成立.
|
关 键 词: | Graham猜想 Descartes积 完全二部图 pebbling |
收稿时间: | 2000-09-01 |
修稿时间: | 2000-09-01 |
本文献已被 万方数据 等数据库收录! |
| 点击此处可从《中国科学A辑》浏览原始摘要信息 |
|
点击此处可从《中国科学A辑》下载免费的PDF全文 |
|