Geodetsko število medianskih grafov

diplomsko delo

Sanja Lakner (Avtor), Aleksandra Tepeh (Mentor)

Povzetek

Množico točk S grafa G = (V(G),E(G)) imenujemo geodetska množica v G, če vsako vozlišče grafa G leži na neki najkrajši poti med dvema vozliščema iz množice S. Diplomsko delo preučuje lastnosti minimalnih geodetskih množic v medianskih grafih, ki so definirani kot grafi, v katerih za poljubna tri vozlišča u, v,w%V(G) presek I(u,v)%I(u,w)%I(v,w) sestoji iz natanko enega vozlišča. Prvo poglavje vsebuje osnovne definicije in opažanja s področja teorije grafov, ki so pomembna za nadaljnje razumevanje. V drugem poglavju so predstavljene osnovne lastnosti medianskih grafov, osredotočili smo se predvsem na dva podrazreda medianskih grafov imenovana kot hiperkocke in drevesa, medianske grafe pa smo karakterizirali s pomočjo periferne ekspanzije. V tretjem poglavju je predstavljeno geodetsko število grafov, v zadnjem pa predstavimo še minimalne geodetske množice v medianskih grafih, preučevane skozi postopek periferne ekspanzije. Karakterizirani so še primeri, ko geodetsko število tudi po postopku periferne ekspanzije ostane enako. Nalogo zaključimo s karakterizacijo medianskih grafov, ki imajo geodetsko število enako 2.

Ključne besede

matematika;geodezija;geodetska števila;medianski grafi;periferna ekspanzija;množice;diplomska dela;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2011
Izvor:	Maribor
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[S. Lakner]
UDK:	51(043.2)
COBISS:	18508040
Št. ogledov:	2260
Št. prenosov:	186
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	The geodetic number of median graphs
Sekundarni povzetek:	A set of vertices S in a graph is called geodetic, if every vertex of a graph lies on some shortest path between two vertices from S. Graduation thesis investigates the properties of minimum geodetic sets in median graphs that are defined as graphs in which for every triple of vertices u,v,w%V(G) the intersection I(u,v)%I(u,w)%I(v,w) consists of precisely one vertex. The first part contains basic definitions and observations from the area of graph theory that are needed in what follows. In the second part basic properties of median graphs are presented where the focus is on two important subclasses of median graphs, namely hypercubes and trees, and median graphs are characterized via peripheral expansion. Section 3 introduces the concept of the geodetic number of a graph, and in the last section minimum geodetic sets in median graphs are studied with respect to the operation of peripheral expansion. The cases when the geodetic number remains the same after the procedure of peripheral expansion are characterized. In the end we characterize median graphs that possess a geodetic set of size two.
Sekundarne ključne besede:	median graphs;peripheral expansion;gated sets;geodetic set;geodetic number;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Diplomsko delo
Komentar na gradivo:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	45 f.
Ključne besede (UDK):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	19367