O'Reilly logo

Analysis of Complex Networks by Frank Emmert-Streib, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

images

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

images

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required