The polynomial characterization of tope graphs of the lopsided sets

Source abstract

The cube polynomial $C_G(x)$ generates the number of $k$-cubes on a graph $G$. As a subclass of partial cubes, the tope graphs of lopsided sets (LOPs) generalize daisy cubes and median graphs. In this paper, we prove that every tope graph of a LOP shares its cube polynomial with some daisy cube, thereby answering affirmatively a problem posed earlier by the authors. Furthermore, we present explicit expressions for the cube polynomials of tope graphs of LOPs: $C_G(x)=f_\mathcal{K}(x+1)$, where $f_\mathcal{K}(x)$ is the $f$-polynomial of the cubical complex $\mathcal{K}$ of $G$. Finally, we show that a class $\mathcal{G}$ of partial cubes is the class of tope graphs of LOPs if and only if the following equivalent conditions hold: (a) $\mathcal{G}$ is the maximal pc-minor-closed class such that every graph in $\mathcal{G}$ has the same cube polynomial as some daisy cube; (b) for every $G\in\mathcal{G}$, each antipodal subgraph of $G$ has the same cube polynomial as some daisy cube.