Root cubes and two-vertex deletions from daisy grids

Abstract

Daisy cubes are finite partial cubes that admit an isometric hypercube embedding whose labels form a Boolean down-set. Call a vertex a root if it can receive the all-zero label in such an embedding. Using the peripheral $\Theta$-class characterization implicit in earlier work of Taranenko and of Xie--Xu, and Vesel's description of possible zero vertices, we prove the following intrinsic refinement. If exactly $b$ classes are peripheral on both sides, then $G\cong G_0\square Q_b$, where $G_0$ has a unique root and the roots of $G$ induce the displayed convex $b$-cube. Our main results concern the daisy grids $B_{r,s}=P_3^{\square r}\square Q_s$. We classify every nonempty graph $B_{r,s}-\{x,y\}$ that is a partial cube, a daisy cube, or a minimal forbidden partial-cube minor for daisy cubes. The ambient-isometric cases admit a uniform coordinate description. A local four-cycle argument reduces every non-isometric noncorner partial-cube deletion to $r+s\le 3$, and an exact orbit analysis leaves precisely eleven sporadic orbits. None is daisy or pc-minor-minimal. Consequently, a deletion is pc-minor-minimal non-daisy exactly when the deleted vertices are opposite corners with $s\ge 1$ and $2r+s\ge 3$, or when a boundary $P_3$-edge is deleted from $B_{1,1}$. This recovers the known hypercube and one-$P_3$ examples and produces a new infinite family with at least two $P_3$-factors. A dependency-free program provides exact certificates for the finite orbit analysis.

19 pages