Rast v grafih

Povzetek

Ključne besede

Podatki

Jezik:	Slovenski jezik
Leto izida:	2009
Tipologija:	2.08 - Doktorska disertacija
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[P. Lukšič]
UDK:	519.17(043.3)
COBISS:	7531092
Št. ogledov:	30
Št. prenosov:	3
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Growth in graphs
Sekundarni povzetek:	The thesis explores the concept of growth in graphs and some similar concepts, such as the distance of a vertex or a graph, distance-balanced graphs, distance-residual subgraphs and the distance distribution of a graph. It offers a uniform view of the field of growth in graphs, ranging from the definition of the term, old and new results on the subject to the open problems, waiting to be solved. A natural generalization of two basic notions in graph theory, adjacency and distance, leads to the notion of distance degree, which tells us the number of vertices at a specific distance from the chosen vertex, called also the growth. The term derives from group theory and was carried over to graph theory through Cayley graphs, where it was first used to study the increasing number of vertices with regard to the distance from the root, i.e.the rate of growth. The research of growth has been done independently in the cases of finite and infinite locally finite graphs from the beginning to this day. Accordingly, each field gets its chapter in the thesis. In the infinite case we start with a section on growth in groups, which is followed by the definition of different forms of growth in graphs and their rate of growth. Then, we research the behavior in product graphs and finish with an algorithm for calculating the growth in infinite graphs, which is used on a family of semiregular tessellations of the Euclidean plane. In the fourth chapter we study growth in finite graphs. First we concentrate on graphs with regular growth (DDR-graphs), analyzing their properties, symmetries and their product graphs. Later, we do the same for distance-balanced graphs, where we also prove the NP-completeness of the distance-balanced addition problem and the existence of infinite families of distance-balanced graphs that are not DDR-graphs. Furthermore, we introduce the notion of a distance-residual subgraph and analyze it. The fifth chapter is meant to show the use of growth in practice, especially in mathematical chemistry and computer science. We present an algorithm for calculating the Hosoya polynomial of a vertex in a catacondensed benzenoid graph. At the end, we summarize the content and present new original contributions to science accompanied with some open problems.
Sekundarne ključne besede:	growth in graphs;spherical growth;ball growth;distance degree sequence;DDR-graph;distance-balanced graph;distance-residual subgraph;growth in product graphs;topological index;computer science;doctoral dissertations;theses;Grafi;Disertacije;
Vrsta datoteke:	application/pdf
Vrsta dela (COBISS):	Doktorska disertacija
Komentar na gradivo:	Univ. Ljubljana, Fak. za računalništvo in informatiko
Strani:	130 str.
ID:	23914174