| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Show document

Title:Povezanost v produktih grafov
Authors:Cigula, Sandra (Author)
Špacapan, Simon (Mentor) More about this mentor... New window
Files:.pdf MAG_Cigula_Sandra_2016.pdf (3,58 MB)
MD5: 9C3D2387F536433C38DD1054C008D232
 
Language:Slovenian
Work type:Master's thesis (m2)
Typology:2.09 - Master's Thesis
Organization:FNM - Faculty of Natural Sciences and Mathematics
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:produkti grafov, kartezični produkt, direktni produkt, krepki produkt, leksikografski produkt, povezanost.
Year of publishing:2016
Publisher:[S. Cigula]
Source:Borovci
UDC:519.171(043.2)
COBISS_ID:22455560 New window
NUK URN:URN:SI:UM:DK:8VEMNVBX
Views:847
Downloads:108
Metadata:XML RDF-CHPDL DC-XML DC-RDF
Categories:FNM
:
  
Average score:(0 votes)
Your score:Voting is allowed only for logged in users.
Share:AddThis
AddThis uses cookies that require your consent. Edit consent...

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Secondary language

Language:English
Title:Connectivity of graph products
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.
Keywords:graphs products, Cartesian product, direct product, strong product, lexicographic product, connectivity.


Comments

Leave comment

You have to log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica