Computing bounds on product graph pebbling numbers
Computing bounds on product graph pebbling numbers
复制标题
DOI：
10.1016/j.tcs.2019.09.050
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Franklin Kenter;Daphne E. Skipper;Dan Wilson
中科院分区：
文献类型：
--
作者：
Franklin Kenter;Daphne E. Skipper;Dan Wilson
给定一个pebble分布到图的顶点，pebbling移动从一个顶点移除两个pebble，并将一个pebble放在相邻的顶点上。pebbling数π（G）是最小的数，使得对于任意π（G）pebbles到G的顶点的分布和G的根点r的选择，存在一个pebbling移动序列，将pebbling放置在r上。计算π（G）是可证明困难的，并且最近用于界定π（G）的方法已被证明在计算上难以处理，即使是中等大小的图。Graham证明了π（G□ H）≤ π（G）π（H），其中G□ H是G和H的笛卡尔积（1989）.虽然这个猜想已经在特定的图族中得到了验证，但一般来说它仍然是开放的。本研究的重点是开发一种计算上易于处理的，基于IP的方法来生成π（G□ H）的良好界限，其目标是阐明Graham猜想。我们提供计算结果的各种笛卡尔积图，包括一些已知的满足格雷厄姆猜想和一些不。我们的方法导致了一个相当大的改进最知名的界π（L□ L），其中L是Lemke图，L□ L是最小的已知潜在的反例格雷厄姆猜想。
Given a distribution of pebbles to the vertices of a graph, a pebbling move removes two pebbles from a single vertex and places a single pebble on an adjacent vertex. The pebbling number π (G) is the smallest number such that, for any distribution of π (G) pebbles to the vertices of G and choice of root vertex r of G, there exists a sequence of pebbling moves that places a pebble on r. Computing π (G) is provably difficult, and recent methods for bounding π (G) have proved computationally intractable, even for moderately sized graphs. Graham conjectured that π (G□ H)≤ π (G) π (H), where G□ H is the Cartesian product of G and H (1989). While the conjecture has been verified for specific families of graphs, in general it remains open. This study combines the focus of developing a computationally tractable, IP-based method for generating good bounds on π (G□ H), with the goal of shedding light on Graham's conjecture. We provide computational results for a variety of Cartesian-product graphs, including some that are known to satisfy Graham's conjecture and some that are not. Our approach leads to a sizable improvement on the best known bound for π (L□ L), where L is the Lemke graph, and L□ L is among the smallest known potential counterexamples to Graham's conjecture.