20.500.12556/DKUM-51455 The cube polynomial and its derivatives: the case of median graphs Polinom kock in njegovi odvodi: primer medianskih grafov Naj bo ▫$alpha_i(G)$▫ število induciranih ▫$i$▫-kock grafa ▫$G$▫. Tedaj je polinom kock ▫$c(G,x)$▫ grafa ▫$G$▫ definiran z ▫$sum_{i ge 0} alpha_i (G) x_i$▫. Pokazano je, da je vsaka funkcija ▫$f$▫ z dvemi predpisanimi naravnimi lastnostmi do faktorja ▫$f(Q_0,x)$▫ enaka polinomu kock. Vpeljan je tudi odvod ▫$partial G$▫ medianskega grafa ▫$G$▫. Dokazano je, da je polinom kock edina funkcija ▫$f$▫ z lastnostjo ▫$f'(G,z) = f(partial G,x)$▫, če je le ▫$f(G,0) = |V(G)|$▫. Dokazanih je tudi več relacij za medianske grafe, ki posplošujejo prej znane rezultate. Na primer, za vsak ▫$s ge 0$▫ velja ▫$c^{(s)}(G, x+1) = sum_{i ge s} frac{c^{(s)}(G,x)}{(i-s)!}$▫. For ▫$i ge 0$▫, the ▫$i$▫-cube of ▫$Q_i$▫ is the graph on ▫$2^i$▫ vertices representing ▫$0/1$▫ tuples of lenght ▫$i$▫, where two vertices are adjacent whenever the tuples differ in exactly one position. (In particular, ▫$Q_0=K_1$▫.) Let ▫$alpha_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 ▫$sum_{i ge 0} alpha_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 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,z) = f(partial 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 istance, it is shown that for any ▫$s ge 0$▫ we have ▫$c^{(s)}(G, x+1) = sum_{i ge s} frac{c^{(i)}(G,x)}{(i-s)!}$▫, where certain derivatives of the cube polynomial coincide with well-known invariants of median graphs. matematika teorija grafov polinom kock odvod grafa medianski grafi mathematics graph theory cube polynomials graph derivation median graphs true false false Angleški jezik Neznan jezik Delo ni kategorizirano 2015-07-10 14:49:17 2015-07-10 14:49:17 2022-05-30 03:05:53 2019-07-11 07:19:29 2003 0 0 R3 (11 str.) no. 1 Vol. 10 2003 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 6973785 12165977 1077-8926 URN:SI:UM:DK:5YNSNFQS http://www.combinatorics.org/ 1 https://dk.um.si/Dokument.php?lang=slv&id=76015 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0