The Cube Polynomial and its Derivatives: the Case of Median Graphs - Brešar, Boštjan; Klavžar, Sandi; Škrekovski, Riste (The Electronic Journal of Combinatorics, 2003)
For i≥ 0, the i-cube Q_i is the graph on 2^i vertices representing 0/1 tuples of length i, where two vertices are adjacent whenever the tuples differ in exactly one position. (In particular, Q_0 = K_1.) Let α_i(G) be the number of induced i-cubes of a graph G. Then the cube polynomial c(G,x) of G is introduced as _i≥ 0 α_i(G) x^i. It is shown that any function f with two related, natural properties, is up to the factor f(Q_0,x) the cube polynomial. The derivation G of a median graph G is introduced and it is proved that the cube polynomial is the only function f with the property f’(G,x)= f( G, x) provided that f(G,0)=|V(G)|. As the main application of the new concept, several relations that widely generalize previous such results for median graphs are proved. For instance, it is shown that for any s≥ 0 we have c^(s)(G,x+1) = _i≥ s c^(i)(G,x)(i-s)! , where certain derivatives of the cube polynomial coincide with well-known invariants of median graphs.