Analysis of Complex Networks

13.4 Cube Polynomials

Many graph polynomials have been introduced so far. For different examples, see, for instance, the book [37] 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(Q_n, x)= (x+2)ⁿ 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 13.2.1.1, is cubical if every induced hypercube of G is contained in at least one of the members of C. Every ...