On cube-free median graphs

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

Abstract

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.

Keywords

matematika;teorija grafov;medianski graf;kartezični produkt;prepoznavni algoritem;mathematics;graph theory;median graph;cube-free graph;Cartesian product;recognition algoritem;

Data

Language:	English
Year of publishing:	2007
Typology:	1.01 - Original Scientific Article
Organization:	UL FMF - Faculty of Mathematics and Physics
UDC:	519.17
COBISS:	14179417
ISSN:	0012-365X
Views:	45
Downloads:	25
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	O medianskih grafih brez 3-kocke
Secondary abstract:	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.
Secondary keywords:	matematika;teorija grafov;medianski graf;kartezični produkt;prepoznavni algoritem;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 345-351
Volume:	ǂVol. ǂ307
Issue:	ǂiss. ǂ3-5
Chronology:	2007
ID:	1472904