Cubes polynomial and its derivatives
by
Sandi Klavzar
Department of Mathematics, PEF, University of Maribor, Koroska 160, 2000 Maribor, Slovenia
Coauthors: Bostjan Bresar (University of Maribor, Slovenia), Riste Skrekovski (University of Ljubljana, Slovenia)

Let \alpha_i(G) be the number of induced i-cubes of a graph G. Then the cubes polynomial c(G, x) of G is introduced as \sum_{i >= 0} \alpha_i(G) xⁱ. It is shown that any function f with two related, natural properties, is up to the factor f(K₁, x) the cubes polynomial. The derivation \partial G of a median graph G is also introduced and it is proved that the cubes polynomial is the only function f with the property f'(G, x) = f(\partial G, x) provided that f(G, 0)=|V(G)|. Several relations that generalize many previous results for median graphs are also given. For instance, for any s >= 0 we have c^(s)(G, x+1) = \sum_{i >= s} [(c⁽ⁱ⁾(G, x))/((i-s)!)] .

Date received: March 16, 2001