20.500.12556/DKUM-49369 Roots of cube polynomials of median graphs Koreni polinoma kock medianskih grafov Polinom kock ▫$c(G,X)$▫ grafa ▫$G$▫ je definiran z ▫$sum_{i ge 0}alpha_i(G)x^i$▫, kjer ▫$alpha_i(G)$▫ označuje število induciranih ▫$i$▫-kock v ▫$G$▫. Naj bo ▫$G$▫ medianski graf. Dokazano je, da je vsaka racionalna ničla polinoma ▫$c(G,x)$▫ oblike ▫$-frac{t+1}{t}$▫ za neko celo število ▫$t>0$▫ in da ima ▫$c(G,x)$▫ vedno realno ničlo na intervalu ▫$[-2,-1)$▫. Nadalje ima ▫$c(G,x)$▫ ▫$p$▫-kratno ničlo natanko tedaj, ko je ▫$G$▫ kartezični produkt ▫$p$▫ dreves istega reda. Grafi acikličnih kubičnih kompleksov so karakterizirani kot grafi za katere velja ▫$c(H,-2)=0$▫ za vsak 2-povezan konveksen podgraf ▫$H$▫. The cube polynomial ▫$c(G,X)$▫ of a graph ▫$G$▫ is defined as ▫$sum_{i ge 0}alpha_i(G)x^i$▫, where ▫$alpha_i(G)$▫ denotes the number of induced ▫$i$▫-cubes of ▫$G$▫, in particular, ▫$alpha_0(G) = |V(G)|$▫ and ▫$alpha_1(G) = |E(G)|$▫. Let ▫$G$▫ be a median graph. It is proved that every rational zero of ▫$c(G,x)$▫ is of the form ▫$-frac{t+1}{t}$▫ for some integer ▫$t>0$▫ and that ▫$c(G,x)$▫ always has a real zero in the interval ▫$[-2,-1)$▫. Moreover, ▫$c(G,x)$▫ has a ▫$p$▫-multiple zero if and only if ▫$G$▫ is the cartesian product of ▫$p$▫ trees all of the same order. Graphs of acyclic cubical complexes are characterized as the graphs ▫$G$▫ for which ▫$c(H,-2)=0$▫ holds for every 2-connected convex subgraph ▫$H$▫ of ▫$G$▫. Median graphs that are Cartesian products are also characterized. matematika teorija grafov polinom kock koren medianski graf kartezični produkt grafov mathematics graph theory cube polynomial root median graph Cartesian product true false false Angleški jezik Neznan jezik Delo ni kategorizirano 2015-07-10 11:58:55 2015-07-10 11:58:55 2022-05-27 03:09:26 2019-07-10 21:28:15 2003 0 0 str. 1-14 št. 887 Vol. 41 2003 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1318-4865 519.17 44310272 12590937 URN:SI:UM:DK:QD0MTRJO http://www.imfm.si/preprinti/PDF/00887.pdf 1 https://dk.um.si/Dokument.php?lang=slv&id=73928 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0