Boštjan Brešar (Author)

Abstract

Skoraj medianski grafi in semi-medianski grafi sta dve naravni posplošitvi dobro znanega razreda medianskih grafov. V članku dokažemo, da je semi-medianski graf skoraj medianski, če in samo če ne vsebuje konveksnega cikla dolžine večje kot štiri.

Keywords

matematika;teorija grafov;medianski graf;konveksen cikel;delna kocka;mathematics;graf theory;median graph;convex cycle;partial cube;

Data

Language: English
Year of publishing:
Typology: 1.01 - Original Scientific Article
Organization: UM FERI - Faculty of Electrical Engineering and Computer Science
UDC: 519.17
COBISS: 14253401 Link will open in a new window
ISSN: 0195-6698
Views: 38
Downloads: 19
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: Unknown
Secondary title: Karakterizacija skoraj medianskih grafov
Secondary abstract: Almost-median and semi-median graphs are two natural generalizations of the well-known class of median graphs. In this note we prove that a semi-median graph is almost-median if and only if it does not contain any convex cycle of length greater than four.
URN: URN:SI:UM:
Type (COBISS): Not categorized
Pages: str. 916-920
Volume: ǂVol. ǂ28
Issue: ǂno. ǂ3
Chronology: 2007
ID: 1473042