A bipartite-subgraph-free bound for pebbling numbers of direct graph products

Let GG and HH be connected graphs, with GK1G\ne K_1 and HH nonbipartite. Let G×HG\times H denote the direct product of graphs, and let π(G)\pi(G) denote the pebbling number.

Direct-product pebbling conjecture.

π(G×H)916π(G)π(H)2.\pi(G\times H)\leq \frac{9}{16}\pi(G)\pi(H)^2.

The conjecture seeks to remove the use of chosen connected spanning bipartite subgraphs from the preceding results for direct products. The paper presents the inequality as an expected analogous bound, and it remains unresolved in the source.

Sources & referencesView supporting material

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.