Roots of cube polynomials of median graphs

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

Abstract

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

Keywords

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

Data

Language:	English
Year of publishing:	2006
Typology:	1.01 - Original Scientific Article
Organization:	UL FMF - Faculty of Mathematics and Physics
UDC:	519.17
COBISS:	13960537
ISSN:	0364-9024
Views:	883
Downloads:	75
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Unknown
Secondary title:	Koreni polinoma kock medianskih grafov
Secondary abstract:	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.
Secondary keywords:	matematika;teorija grafov;polinom kock;koren;medianski graf;kartezični produkt grafov;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 37-50
Volume:	ǂVol. ǂ52
Issue:	ǂno. ǂ1
Chronology:	2006
ID:	1472655