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:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UL FMF - Fakulteta za matematiko in fiziko
UDK: 519.17
COBISS: 14179417 Povezava se bo odprla v novem oknu
ISSN: 0012-365X
Št. ogledov: 45
Št. prenosov: 25
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

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
Priporočena dela:
, ni podatka o podnaslovu
, ni podatka o podnaslovu
, ni podatka o podnaslovu
, ni podatka o podnaslovu
, ni podatka o podnaslovu