EISPN conjectures for Cartesian products of paths

From papers

Let PmP_m denote the path of order mm, and let \Box denote the Cartesian graph product. For a graph GG, let EISPN(G)EISPN(G) denote its efficient isolated private-neighborhood number.

EISPN path-product conjectures. If k1k \ge 1, then

EISPN(P3P2k)=6k.EISPN(P_3 \mathbin{\Box} P_{2k})=6k.

If m2m \ge 2, then

EISPN(P4Pm)=4m.EISPN(P_4 \mathbin{\Box} P_m)=4m.

These conjectures are posed from data for graph classes. The source gives no resolution; the first EISPN assertion is presented as an additional conjecture following the EIPN grid conjecture.

Progress summary

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

Sources & referencesView supporting material

Primary source

Stephen T. Hedetniemi and Douglas F. Rall, “On maximizing private neighbors in graphs”, arXiv:2511.07248 (2025).

Solutions 0

No solutions have been posted yet.