Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.29577 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911556736909312 |
|---|---|
| author | Zheng, Xuan Xie, Yan-Ting Xu, Shou-Jun |
| author_facet | Zheng, Xuan Xie, Yan-Ting Xu, Shou-Jun |
| contents | 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(x,0^n)$ 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)$, we consider the cube polynomial $C_G(x)$, the distance cube polynomial $D_{G,u}(x,y)$, and the polynomial $W_{G,u}(x)$, which count $k$-cubes, $k$-cubes at distance from $u$, and vertices at distance $k$ from $u$, respectively.
In this paper, we prove that for a partial cube $G$ with a vertex $u\in V(G)$, $G$ is a daisy cube and $u=0^n$ if and only if one of the following equivalent conditions holds: (1) $C_{G}(x)=W_{G,u}(x+1)$; (2) $D_{G,u}(x,y)=W_{G,u}(x+y)$; (3) $D_{G,u}(x,y)=C_{G}(x+y-1)$. In particular, conditions (1) and (3) give affirmative answers to two open problems posed by Klavžar and Mollard [European J. Combin., 80 (2019) 214--223]. Further, we obtain that for arbitrary partial cube $G$, $D_{G,u}(x,y)\leq W_{G,u}(x+y)$ and $C_{G}(x)\leq W_{G,u}(x+1)$. Besides, another bound for $C_G(x)$ due to Xie et al. [J. Graph Theory, 106 (2024) 907--922] is given by the clique polynomial $Cl_{G^\#}(x+1)$ of the crossing graph of $G$. We also compare these two bounds and show that the simplex graphs form the unique class of graphs for which the two bounds coincide. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_29577 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Resolving problems on the polynomial identity characterization of daisy cubes Zheng, Xuan Xie, Yan-Ting Xu, Shou-Jun Combinatorics 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(x,0^n)$ 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)$, we consider the cube polynomial $C_G(x)$, the distance cube polynomial $D_{G,u}(x,y)$, and the polynomial $W_{G,u}(x)$, which count $k$-cubes, $k$-cubes at distance from $u$, and vertices at distance $k$ from $u$, respectively. In this paper, we prove that for a partial cube $G$ with a vertex $u\in V(G)$, $G$ is a daisy cube and $u=0^n$ if and only if one of the following equivalent conditions holds: (1) $C_{G}(x)=W_{G,u}(x+1)$; (2) $D_{G,u}(x,y)=W_{G,u}(x+y)$; (3) $D_{G,u}(x,y)=C_{G}(x+y-1)$. In particular, conditions (1) and (3) give affirmative answers to two open problems posed by Klavžar and Mollard [European J. Combin., 80 (2019) 214--223]. Further, we obtain that for arbitrary partial cube $G$, $D_{G,u}(x,y)\leq W_{G,u}(x+y)$ and $C_{G}(x)\leq W_{G,u}(x+1)$. Besides, another bound for $C_G(x)$ due to Xie et al. [J. Graph Theory, 106 (2024) 907--922] is given by the clique polynomial $Cl_{G^\#}(x+1)$ of the crossing graph of $G$. We also compare these two bounds and show that the simplex graphs form the unique class of graphs for which the two bounds coincide. |
| title | Resolving problems on the polynomial identity characterization of daisy cubes |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2603.29577 |