Povzetek

Množica ▫$S$▫ vozlišč grafa ▫$G$▫ je geodetska, če vsako vozlišče grafa ▫$G$▫ leži na intervalu med dvema vozliščema iz ▫$S$▫. Velikost najmanjše geodetske množice grafa ▫$G$▫ se imenuje geodetsko število ▫$g(G)$▫ grafa ▫$G$▫. V članku dokažemo, da geodetsko število leksikografskega produkta ▫$G \circ H$▫, kjer ▫$H$▫ ni poln graf, leži med 2 in ▫$3g(G)$▫. Okarakteriziramo vse grafe ▫$G$▫ in ▫$H$▫, za katere je ▫$G \circ H = 2$▫, kot tudi leksikografske produkte ▫$T \circ H$▫, za katere je ▫$g(T \circ H) = 3g(G)$▫, kjer je ▫$T$▫ izomorfen drevesu. Z uporabo novega koncepta geodominantnih trojic grafa ▫$G$▫ najdemo formulo, ki določi točno geodetsko število ▫$G \circ H$▫, kjer je ▫$G$▫ poljuben graf in ▫$H$▫ graf, ki ni poln.

Ključne besede

matematika;teorija grafov;leksikografski produkt;geodetsko število;geodominantna trojica;mathematics;graph theory;lexicographic product;geodetic number;geodominating triple;

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: 15929945 Povezava se bo odprla v novem oknu
ISSN: 0012-365X
Št. ogledov: 311
Št. prenosov: 24
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: Angleški jezik
Sekundarni naslov: Geodetsko število leksikografskih produktov grafov
Sekundarni povzetek: A set ▫$S$▫ of vertices of a graph ▫$G$▫ is a geodetic set if every vertex of ▫$G$▫ lies in an interval between two vertices from ▫$S$▫. The size of a minimum geodetic set in ▫$G$▫ is the geodetic number ▫$g(G)$▫ of ▫$G$▫. We find that the geodetic number of the lexicographic product ▫$G \circ H$▫ for a non-complete graph ▫$H$▫ lies between 2 and ▫$3g(G)$▫. We characterize the graphs ▫$G$▫ and ▫$H$▫ for which ▫$G \circ H = 2$▫, as well as the lexicographic products ▫$T \circ H$▫ that enjoy ▫$g(T \circ H) = 3g(G)$▫, when ▫$T$▫ is isomorphic to a tree. Using a new concept of the so-called geodominating triple of a graph ▫$G$▫, a formula that expresses the exact geodetic number of ▫$G \circ H$▫ is established, where ▫$G$▫ is an arbitrary graph and ▫$H$▫ a non-complete graph.
Sekundarne ključne besede: matematika;teorija grafov;leksikografski produkt;geodetsko število;geodominantna trojica;
URN: URN:SI:UM:
Vrsta dela (COBISS): Delo ni kategorizirano
Strani: str. 1693-1698
Letnik: Vol. 311
Zvezek: iss. 16
Čas izdaje: 2011
ID: 1475488
Priporočena dela:
, ni podatka o podnaslovu
, ni podatka o podnaslovu