Roots of cube polynomials of median graphs

Boštjan Brešar (Avtor), Sandi Klavžar (Avtor), Riste Škrekovski (Avtor)

Povzetek

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

Ključne besede

matematika;teorija grafov;polinom kock;koren;medianski graf;kartezični produkt grafov;mathematics;graph theory;cube polynomial;root;median graph;Cartesian product;

Podatki

Jezik:	Angleški jezik
Leto izida:	2006
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
UDK:	519.17
COBISS:	13960537
ISSN:	0364-9024
Št. ogledov:	883
Št. prenosov:	75
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Neznan jezik
Sekundarni naslov:	Koreni polinoma kock medianskih grafov
Sekundarni povzetek:	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.
Sekundarne ključne besede:	matematika;teorija grafov;polinom kock;koren;medianski graf;kartezični produkt grafov;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 37-50
Letnik:	ǂVol. ǂ52
Zvezek:	ǂno. ǂ1
Čas izdaje:	2006
ID:	1472655