The polynomial characterization of tope graphs of the lopsided sets

Xuan Zheng; Yan-Ting Xie; Shou-Jun Xu

In the authors' words

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_{K} (x + 1)$ , where $f_{K} (x)$ is the $f$ -polynomial of the cubical complex $K$ of $G$ . Finally, we show that a class $G$ of partial cubes is the class of tope graphs of LOPs if and only if the following equivalent conditions hold: (a) $G$ is the maximal pc-minor-closed class such that every graph in $G$ has the same cube polynomial as some daisy cube; (b) for every $G \in G$ , each antipodal subgraph of $G$ has the same cube polynomial as some daisy cube.

Main resultThe abstract does not state a limitation.

The polynomial characterization of tope graphs of the lopsided sets

In the authors' words

More on Combinatorics & discrete math that day

Circular s-choice parking functions: an exact closed formula via rotational symmetry

Single-Fragment Forensic Coding via Multidimensional Cyclically Permutable Codes

The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach

Proof of Almkvist's conjecture on the unimodality of partition polynomials

On infinite families of [Pn​]-irregular graphs

On infinite families of $[P_{n}]$ -irregular graphs