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:
Typology: 0 - Not set
Organization: UL FMF - Faculty of Mathematics and Physics
UDC: 519.17
COBISS: 12590937 Link will open in a new window
ISSN: 1318-4865
Views: 47
Downloads: 8
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: Slovenian
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. 1-14
Volume: ǂVol. ǂ41
Issue: ǂšt. ǂ887
Chronology: 2003
ID: 66368
Recommended works:
, no subtitle data available
, no subtitle data available
, no subtitle data available
, no subtitle data available