Strong-product variation of Graham's pebbling conjecture

About 8 years old · traced to

Let GG and HH be connected graphs, let G⊠HG\boxtimes H denote their strong product, and let π(G)\pi(G) denote the pebbling number of a graph. The notation ∣G∣|G| and ∣H∣|H| denotes the numbers of vertices of GG and HH, respectively.

Strong-product pebbling conjecture. For any connected graphs GG and HH,

π(G⊠H)≤max⁡{12π(G)π(H), ∣G∣∣H∣}+2.\pi(G\boxtimes H)\leq \max\left\{\frac{1}{2}\pi(G)\pi(H),\ |G||H|\right\}+2.

This is proposed as a variation of Graham's conjecture for strong products. The paper gives motivating bounds and an example showing that a simpler factor-12\frac12 bound does not hold, while this sharper variation remains unresolved in the source.

References

Primary source

John Asplund, Glenn Hurlbert and Franklin Kenter, “Pebbling on Graph Products and other Binary Graph Constructions”, arXiv:1801.07808 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.