Resolving problems on polynomial characterizations of daisy cubes and extensions

Abstract

Let $X\subseteq \{0,1{\}}^n$ be a set of binary strings of length $n$. The daisy cube $Q_n(X)$ is the subgraph of the hypercube $Q_n$ induced by the union of the intervals $I(0^n,x)$ for $x\in X$. As a subclass of partial cubes, it generalizes Fibonacci cubes and Lucas cubes. For a graph $G$ and a vertex $u\in V(G)$, the generating function of the number of $k$-cubes (resp. $k$-cubes at distance $d$ from $u$, and vertices at distance $d$ from $u$) is called the cube polynomial $C_G(x)$ (resp. the distance cube polynomial $D_{G,u}(x,y)$, and the distance polynomial $W_{G,u}(x)$). Let $G$ be a partial cube embedded into the hypercube $Q_n$ with $0^n\in V(G)$. In this paper, we prove that $G$ is a daisy cube if and only if one of the following equivalent conditions holds: (1) $C_G(x)=W_{G,0^n}(x+1)$; (2) $D_{G,0^n}(x,y)=W_{G,0^n}(x+y)$; (3) $D_{G,0^n}(x,y)=C_G(x+y-1)$. In particular, the results related to (1) and (3) give affirmative answers to two open problems posed by Klavžar and Mollard (2019). Meanwhile, our results yield non-constructive characterizations of daisy cubes, which answer the question posed by Taranenko (2020). Further, we prove that $D_{G,u}(x,y)\le W_{G,u}(x+y)$ and $C_G(x)\le W_{G,u}(x+1)$ among the whole class of partial cubes. Besides, combined with another sharp upper bound $C{l}_{G^{\#}}(x+1)$ for $C_G(x)$ due to Xie et al.(2024), we obtain polynomial characterizations of simplex graphs (a subclass of daisy cubes): $G$ is a simplex graph if and only if $W_{G,0^n}(x)=C{l}_{G^{\#}}(x)$, here $C{l}_{G^{\#}}(x)$ is the clique polynomial of the crossing graph $G^{\#}$ of $G$.