Povezanost v produktih grafov

magistrsko delo

Sandra Cigula (Author), Simon Špacapan (Mentor)

Abstract

V tej nalogi bomo obravnavali pojma povezanost po povezavah in povezanost po vozliščih v produktih grafov. Drugi cilj bo opisati strukturo in ostale lastnosti najmanjših presečnih množic vozlišč in najmanjših presečnih množic povezav v produktih grafov. Osredotočili se bomo predvsem na kartezični, direktni, krepki in leksikografski produkt grafov. Zanimalo nas bo, kako izraziti povezanost produkta z lastnostmi posameznih faktorjev produkta, kot so najmanjša stopnja, red grafa in povezanost. Pri direktnem produktu grafov bomo ugotovili, da je povezanost po povezavah odvisna od povezanosti faktorjev, pa tudi od tega, kako daleč sta faktorja $G$ in $H$ od tega, da bi bila dvodelna. Nato bomo obravnavali velikost in strukturo najmanjših presečnih množic povezav kartezičnih produktov grafov. Podan bo dokaz trditve $lambda(G , Box , H)= textrm{min}left{lambda(G)left|V(H)right|,lambda(H)left|V(G)right|,delta(G)+delta(H)right}.$ Dokaz podobne trditve za povezanost po vozliščih kartezičnega produkta bo naveden v nadaljevanju. Na koncu bomo obravnavali velikost in strukturo najmanjših presečnih množic povezav krepkih produktov grafov in povezanost v leksikografskem produktu.

Keywords

magistrska dela;produkti grafov;kartezični produkt;direktni produkt;krepki produkt;leksikografski produkt;povezanost;

Data

Language:	Slovenian
Year of publishing:	2016
Typology:	2.09 - Master's Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[S. Cigula]
UDC:	519.171(043.2)
COBISS:	22455560
Views:	1024
Downloads:	135
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Connectivity of graph products
Secondary abstract:	In this thesis we discuss edge and vertex connectivities of graph products. The aim is to determine the connectivity of all four standard graph products and describe the structure of minimum edge-cut sets. We will study how to express the connectivity of the product with properties of its factors, such as minimum degree, order and connectivity. For the edge connectivity of direct product of graphs we find that connectivity of the product depends not only on connectivities of its factors but also on how far the factors $G$ and $H$ are from being bipartite. Then we discuss the structure and other properties of minimum edge-cuts in Cartesian product of graphs. We present the proof of the following result $lambda(G , Box , H)= textrm{min}left{lambda(G)left\|V(H)right\|,lambda(H)left\|V(G)right\|,delta(G)+delta(H)right}.$ Proof of a similar claim for vertex connectivity of Cartesian products of graphs will also be presented. Finally we consider the size and the structure of minimum edge-cuts in strong products of graphs and edge and vertex connectivities of lexicographic product.
Secondary keywords:	graph products;Cartesian product;direct product;strong product;lexicographic product;connectivity;master theses;
URN:	URN:SI:UM:
Type (COBISS):	Master's thesis
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	XI, 68 str.
ID:	9137753