On the geodetic number and related metric sets in Cartesian product graphs

Boštjan Brešar (Author), Sandi Klavžar (Author), Aleksandra Tepeh (Author)

Abstract

Množica vozlišč ▫$S$▫ grafa ▫$G$▫ je geodetska množica, če vsako vozlišče grafa ▫$G$▫ leži na vsaj enem intervalu med vozliščema iz ▫$S$▫. Moč najmanjše geodetske množice v ▫$G$▫ imenujemo geodetsko število grafa ▫$G$▫. Dokazana je zgornja meja za geodetsko število kartezičnega produkta in za nekatere razrede grafov je dobljena tudi natančna vrednost. Prav tako je dokazano, da imajo mnoge metrično definirane množice v kartezičnih produktih produktno strukturo in da je konturna množica v kartezičnem produktu geodetska natanko tedaj, ko sta njeni projekciji geodetski množici v faktorjih.

Keywords

matematika;teorija grafov;kartezični produkt;geodetsko število;geodetska množica;konturna množica;mathematics;graph theory;Cartesian product;geodetic number;geodetic set;contour set;

Data

Language:	English
Year of publishing:	2008
Typology:	1.01 - Original Scientific Article
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
UDC:	519.17
COBISS:	14936409
ISSN:	0012-365X
Views:	685
Downloads:	91
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Unknown
Secondary title:	Geodetsko število in sorodne metrične množice v kartezičnih produktih grafov
Secondary abstract:	A set ▫$S$▫ of vertices of a graph ▫$G$▫ is a geodetic set if every vertex of ▫$G$▫ lies in at least one interval between the vertices of ▫$S$▫. The size of a minimum geodetic set in ▫$G$▫ is the geodetic number of ▫$G$▫. Upper bounds for the geodetic number of Cartesian product graphs are proved and for several classes exact values are obtained. It is proved that many metrically defined sets in Cartesian products have product structure and that the contour set of a Cartesian product is geodetic if and only if their projections are geodetic sets in factors.
Secondary keywords:	matematika;teorija grafov;kartezični produkt;geodetsko število;geodetska množica;konturna množica;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 5555-5561
Volume:	ǂVol. ǂ308
Issue:	ǂiss. ǂ23
Chronology:	2008
ID:	1474026