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: |
2003 |
Typology: |
0 - Not set |
Organization: |
UL FMF - Faculty of Mathematics and Physics |
UDC: |
519.17 |
COBISS: |
12590937
|
ISSN: |
1318-4865 |
Views: |
47 |
Downloads: |
8 |
Average score: |
0 (0 votes) |
Metadata: |
|
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 |