路与圈的优化t-pebbling数

doi:10.3969/j.issn.0253-2778.2015.03.002

中国科学技术大学学报 ›› 2015, Vol. 45 ›› Issue (3): 186-192.DOI: 10.3969/j.issn.0253-2778.2015.03.002

• 论著 • 上一篇

路与圈的优化t-pebbling数

夏正江，潘永亮，徐俊明

中国科学技术大学数学科学学院，安徽合肥 230026

收稿日期:2014-11-14 修回日期:2015-03-10 接受日期:2015-03-10 出版日期:2015-03-10 发布日期:2015-03-10

Optimal t-pebbling on paths and cycles

XIA Zhengjiang, PAN Yongliang, XU Junming

School of Mathematical Sciences, University of Science and Technology of China, Hefei 230026, China

Received:2014-11-14 Revised:2015-03-10 Accepted:2015-03-10 Online:2015-03-10 Published:2015-03-10
Contact: PAN Yongliang
About author:XIA Zhengjiang, male, born in 1987, PhD candidate. Research field: combinatorics and graph theory.
Supported by:
Supported by the Fundamental Research Funds for the Central Universities and the NNSF of China (61272008,11271348,10871189).

摘要/Abstract

摘要： 图上的一个pebbling移动,是从图的一个顶点同时移除2个pebbles,并且在其某个邻点上放置1个pebble. 图的优化t-pebbling数，记为f′t(G), 是指图G中所需要的pebbled的最小数目，使得存在该f′t(G)个pebbles在图上的一种分布，可以在经过一系列pebbling移动后，t个pebbles可以移动到任意一个给定的目标顶点上.f′(G)=f′1(G)称为图G的优化pebbling数.这里给出了路Pn和圈C5的优化t-pebbling数，证明了f′9t(P2×P3)=20t；f′9t+1(P2×P3)=20t+3；当2≤r≤8时，20t+2r+1≤f′9t+r(P2×P3) ≤20t+2r+2，其中，当5≤r≤8时，最后一个不等式取到等号.

关键词: 优化t-pebbling数, 路, 圈, 笛卡尔乘积

Abstract: A pebbling move removes two pebbles from a vertex and places one pebble on one of its neighbours. For t≥1, the optimal t-pebbling number of a graph G, f′t(G), is the minimum number of pebbles necessary so that from some initial distribution of them it is possible to move t pebbles to any target vertex by a sequence of pebbling moves. f′(G)=f′1(G) be the optimal pebbling number of G. Here the optimal t-pebbling numbers of the path Pn and the cycle C5 were given, respectively. In the final section, it was obtained that f′9t(P2×P3)=20t, f′9t+1(P2×P3)=20t+3, and 20t+2r+1≤f′9t+r(P2×P3)≤20t+2r+2, for 2≤r≤8, the last equality holds for r=5,6,7,8.

Key words: optimal t-pebbling number, path, cycle, Cartesian product

中图分类号:

O157.

夏正江，潘永亮，徐俊明. 路与圈的优化t-pebbling数[J]. 中国科学技术大学学报, 2015, 45(3): 186-192.

XIA Zhengjiang, PAN Yongliang, XU Junming. Optimal t-pebbling on paths and cycles[J]. Journal of University of Science and Technology of China, 2015, 45(3): 186-192.

[1]	火清羿. 染色数为5和6的图中的圈长[J]. 中国科学技术大学学报, 2021, 51(5): 374-381.
[2]	王宁, 席茂, 周文罡, 李礼, 李厚强. 深度视觉目标跟踪进展综述[J]. 中国科学技术大学学报, 2021, 51(4): 335-344.
[3]	朱巧慧, 梁启鹏, 康宇, 赵云波. 无界DoS攻击下网络控制系统的多路径切换保护[J]. 中国科学技术大学学报, 2021, 51(1): 22-32.
[4]	余磊. 3一致超图中线性哈密顿圈的Ore条件[J]. 中国科学技术大学学报, 2020, 50(5): 669-672.
[5]	剧宏娟，雷英杰. 三圈图和四圈图的最大无符号拉普拉斯分离度[J]. 中国科学技术大学学报, 2020, 50(4): 402-408.
[6]	薛益民，陈守婷. 含指数增长非线性项的椭圆方程的多解性[J]. 中国科学技术大学学报, 2020, 50(3): 300-311.
[7]	齐方鹏, 王童, 傅忠谦. 基于互信息的复杂网络链路预测[J]. 中国科学技术大学学报, 2020, 50(1): 57-63.
[8]	张轩轩，牛国庆，李垣志. 城市公路隧道近火源区质量卷吸速率研究[J]. 中国科学技术大学学报, 2019, 49(4): 329-342.
[9]	干文杰，张举勇，邓建松. 基于多路径优化的视频稳像方法[J]. 中国科学技术大学学报, 2019, 49(3): 237-243.
[10]	张福全，吴寅，杨绪兵. 移动性度量的移动时延容忍网络路由策略[J]. 中国科学技术大学学报, 2019, 49(2): 132-137.
[11]	李江妹，王雨. MODIS漏测的全球洋面液态云水研究[J]. 中国科学技术大学学报, 2019, 49(11): 912-919.
[12]	梁勇，裴利丹，胡夫涛，侯新民. 笛卡尔乘积和直积图的全{k}控制划分数[J]. 中国科学技术大学学报, 2018, 48(8): 605-611.
[13]	齐方鹏，王童，周明洋，傅忠谦. 基于互信息的动态网络链路预测算法研究[J]. 中国科学技术大学学报, 2018, 48(6): 440-446.
[14]	余桂东, 黄冬明, 张午骁, 汪宸. 双圈图和三圈图的最大拉普拉斯分离度[J]. 中国科学技术大学学报, 2017, 47(9): 733-737.
[15]	张玉州，刘晓飞，黄师化，梅俊. 一种求解多车型CARP的有效memetic 算法[J]. 中国科学技术大学学报, 2017, 47(7): 583-593.

路与圈的优化t-pebbling数

Optimal t-pebbling on paths and cycles

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价