文档类型
文章
出版日期
7-10-2012
出版来源
暹罗在离散数学》杂志上
卷号
26
问题数量
3
第一页
919年
最后一页
928年
出版商
工业与应用数学学会的
石头
1095 - 7146
文摘
给出一个简单的连通图,用卵石铺配置是一个函数的顶点设置为非负整数。用卵石铺移动相邻顶点删除两个石子从一个顶点并添加一个石子。一个顶点r据说可以从配置如果存在一系列用卵石铺移动一个石子的地方在r。配置是可以解决的,如果每一个顶点都是可获得的。我们证明严格边界的顶点和两个和三个石子的数量一个直径2图上无法解决的配置可以有图的大小。我们还证明,确定可达性一个顶点的np完备性,即使在直径2的图。
关键字
图用卵石铺,直径2、非完全多项式、AMS主题分类,68篮,68 r05 68 r10
建议引用
库萨克,查尔斯。,蒂莫西·刘易斯,丹尼尔·辛普森and Samuel Taggart. "The Complexity of Pebbling in Diameter Two Graphs*." SIAM Journal on Discrete Mathematics 26, no. 3 (2012): 919-928.
评论
∗编辑收到的8月11日,2011;发表(修订后的形式)4月6日,2012;电子7月10日,2012年出版。这项工作是支持的NSF格兰特DUE0851293之下。