Povzetek

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.

Ključne besede

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;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
UDK: 519.17
COBISS: 14936409 Povezava se bo odprla v novem oknu
ISSN: 0012-365X
Št. ogledov: 685
Št. prenosov: 91
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Neznan jezik
Sekundarni naslov: Geodetsko število in sorodne metrične množice v kartezičnih produktih grafov
Sekundarni povzetek: 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.
Sekundarne ključne besede: matematika;teorija grafov;kartezični produkt;geodetsko število;geodetska množica;konturna množica;
URN: URN:SI:UM:
Vrsta dela (COBISS): Delo ni kategorizirano
Strani: str. 5555-5561
Letnik: ǂVol. ǂ308
Zvezek: ǂiss. ǂ23
Čas izdaje: 2008
ID: 1474026
Priporočena dela:
, ni podatka o podnaslovu
, ni podatka o podnaslovu
, ni podatka o podnaslovu