ǂA ǂcharaterization of planar median graphs

Abstract

Medianski grafi imajo mnogo zanimivih lastnosti. Ena izmed njih je, v povezavi z grafi brez trikotnikov, je časovna zahtevnost za prepoznavanje teh grafov. V splošnem ta zahtevnost ni zelo hitra. Če pa se omejimo na ravninske medianske grafe, je časovna zahtevnost linearna. Kljub temu dejstvu v literaturi ne obstaja karakterizacija ravninskih medianskih grafov. V članku je predstavljen dodaten pogoj h konveksni ekspanziji, ki nam karakterizira ravninske medianske grafe.

Keywords

matematika;teorija grafov;medianski grafi;ravninski grafi;ekspanzija;mathematics;graf theory;median graphs;planar graphs;expansion;

Data

Language:	English
Year of publishing:	2006
Typology:	1.01 - Original Scientific Article
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
UDC:	519.17
COBISS:	14034009
ISSN:	1234-3099
Views:	542
Downloads:	465
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Karakterizacija ravninskih medianskih grafov
Secondary abstract:	Median graphs have many interesting properties. One of them is-in connection with triangle free graphs-the recognition complexity. In general the complexity is not very fast, but if we restrict to the planar case the recognition complexity becomes linear. Despite this fact, there is no characterization of planar median graphs in the literature. Here an additional condition is introduced for the convex expansion procedure that characterizes planar median graphs.
Secondary keywords:	matematika;teorija grafov;medianski grafi;ravninski grafi;ekspanzija;
URN:	URN:SI:UM:
Pages:	str. 41-48
Volume:	ǂVol. ǂ26
Issue:	ǂno. ǂ1
Chronology:	2006
ID:	9595930