Many graph polynomials have been introduced so far. For different examples, see, for instance, the book  and recent surveys [34, 35]. Although most graph polynomials are naturally defined as generating functions of a special type, the reason they have attracted attention is that often algebraic methods allow us to decode some combinatorial information contained in graph polynomials. In this section we survey known results on the cube polynomial. In particular, we survey results on the cube polynomial of special classes of median graphs and give bounds for rational and real zeros for both classes M and M*. A special subclass of median graphs – graphs of acyclic cubical complexes – can be nicely characterized with the roots of their cube polynomials. The Cartesian product of trees of the same order also has a special cube polynomial. Results on higher derivatives are also presented.
Recall that αi(G), i ≥ 1, denotes the number of induced i-cubes of G. The cube polynomial c(G, x) of G is defined as
For instance, c(Qn, x)= (x+2)n and c(T, x)= (n–1) x + n, where T denotes a tree on n vertices. Note also that
Acover C of a graph G, as defined in Subsection 126.96.36.199, is cubical if every induced hypercube of G is contained in at least one of the members of C. Every ...