Povzetek
Naj bo ▫$G$▫ mediansk graf brez 3-kocke. Pokazano je, da velja ▫$\frac{k}{2} \ge \sqrt{n}-1 \ge \frac{m}{2\sqrt{n}} \ge \sqrt{s} \ge r-1$▫, kjer so ▫$n, m, s, k$▫ in ▫$r$▫ števila točk, povezav, kvadratov, ▫$\Theta$▫-razredov in število povezav najmanšega ▫$\Theta$▫-razreda grafa ▫$G$▫. Enakosti so dosežene natanko tedaj, ko je ▫$G$▫ kartezični produkt dveh dreves istega reda. Obravnavan je tudi polinom kock medianskih grafov in pokazano je, da lahko ravninske medianske grafe brez 3-kocke prepoznamo v linearnem času.
Ključne besede
matematika;teorija grafov;medianski graf;kartezični produkt;prepoznavni algoritem;mathematics;graph theory;median graph;cube-free graph;Cartesian product;recognition algoritem;
Podatki
Jezik: |
Angleški jezik |
Leto izida: |
2007 |
Tipologija: |
1.01 - Izvirni znanstveni članek |
Organizacija: |
UL FMF - Fakulteta za matematiko in fiziko |
UDK: |
519.17 |
COBISS: |
14179417
|
ISSN: |
0012-365X |
Št. ogledov: |
45 |
Št. prenosov: |
25 |
Ocena: |
0 (0 glasov) |
Metapodatki: |
|
Ostali podatki
Sekundarni jezik: |
Slovenski jezik |
Sekundarni naslov: |
O medianskih grafih brez 3-kocke |
Sekundarni povzetek: |
Let ▫$G$▫ be a cube-free median graph. It is proved that ▫$\frac{k}{2} \ge \sqrt{n}-1 \ge \frac{m}{2\sqrt{n}} \ge \sqrt{s} \ge r-1$▫, where ▫$n, m, s, k$▫ and ▫$r$▫ are the number of vertices, edges, squares, ▫$\Theta$▫-classes, and the number of edges in a smallest ▫$\Theta$▫-class of ▫$G$▫, respectively. Moreover, the equalities characterize Cartesian product of two trees of the same order. The cube polynomial of cube-free median graphs is also considered and it is shown that planar cube-free median graphs can be recognized in linear time. |
Sekundarne ključne besede: |
matematika;teorija grafov;medianski graf;kartezični produkt;prepoznavni algoritem; |
URN: |
URN:SI:UM: |
Vrsta dela (COBISS): |
Delo ni kategorizirano |
Strani: |
str. 345-351 |
Letnik: |
ǂVol. ǂ307 |
Zvezek: |
ǂiss. ǂ3-5 |
Čas izdaje: |
2007 |
ID: |
1472904 |