On cube-free median graphs

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

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