On the geodetic number of median graphs

Boštjan Brešar (Avtor), Aleksandra Tepeh (Avtor)

Povzetek

Množica vozlišč ▫$S$▫ v grafu se imenuje geodetska množica, če vsako vozlišče tega grafa leži na kaki najkrajši poti med dvema vozliščema iz množice ▫$S$▫. V članku raziskujemo najmanjše geodetske množice medianskih grafov z ozirom na operacijo periferne ekspanzije. Spotoma obravnavamo geodetske množice medianskih prizem in karakteriziramo medianske grafe, ki imajo geodetsko množico velikosti 2.

Ključne besede

matematika;teorija grafov;medianski grafi;geodetsko število;geodetska množica;kartezični produkt grafov;ekspanzija;mathematics;graph theory;median graphs;geodetic number;geodetic set;Cartesian product;geodesic;expansion;

Podatki

Jezik:	Angleški jezik
Leto izida:	2008
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
UDK:	519.17
COBISS:	14811225
ISSN:	0012-365X
Št. ogledov:	39
Št. prenosov:	24
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	O geodetskem številu medianskih grafov
Sekundarni povzetek:	A set of vertices ▫$S$▫ in a graph is called geodetic if every vertex of this graph lies on some shortest path between two vertices from ▫$S$▫. In this paper, minimum geodetic sets in median graphs are studied with respect to the operation of peripheral expansion. Along the way geodetic sets of median prisms are considered and median graphs that possess a geodetic set of size two are characterized.
Sekundarne ključne besede:	matematika;teorija grafov;medianski grafi;geodetsko število;geodetska množica;kartezični produkt grafov;ekspanzija;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 4044-4051
Letnik:	ǂVol. ǂ308
Zvezek:	ǂiss. ǂ18
Čas izdaje:	2008
DOI:	10.1016/j.disc.2007.07.119
ID:	1473677