Geodetsko število medianskih grafov

diplomsko delo

Sanja Lakner (Author), Aleksandra Tepeh (Mentor)

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2011
Source:	Maribor
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[S. Lakner]
UDC:	51(043.2)
COBISS:	18508040
Views:	2260
Downloads:	186
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	The geodetic number of median graphs
Secondary abstract:	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.
Secondary keywords:	median graphs;peripheral expansion;gated sets;geodetic set;geodetic number;
URN:	URN:SI:UM:
Type (COBISS):	Undergraduate thesis
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	45 f.
Keywords (UDC):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	19367