The cube polynomial and its derivatives: The case of median graphs (Q1856347)

For \(i\geq 0\), the \(i\)-cube \(Q_i\) is the graph on \(2^i\) vertices represented by \(i\)-tuples of \(0\)'s and \(1\)'s, where two vertices are adjacent whenever the corresponding \(i\)-tuples differ in exactly one position. Let \(\alpha_i(G)\) be the number of induced \(i\)-cubes of a graph \(G\). Then the cube polynomial \(c(G,x)\) of \(G\) is defined by \(\sum_{i\geq 0} \alpha_i(G)x^i\). The authors give several characterizations of the cube polynomial. In particular, they define the derivation \(\partial G\) of a median graph \(G\) and prove that the cube polynomial is the only function \(c\) with the property \(c'(G,x)= c(\partial G,x)\) provided that \(c(G, 0)=|V(G)|\). The cube polynomial is then used to generalize some of the known results for median graphs.