| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Show document

Title:Nekateri rezultati o povezanosti in neodvisnih množicah v produktih grafov
Authors:Paj Erker, Tjaša (Author)
Špacapan, Simon (Mentor) More about this mentor... New window
Files:.pdf DOK_Paj_Erker_Tjasa_2018.pdf (603,74 KB)
MD5: C65739E32C06F33FF33139397AD7277F
 
Language:Slovenian
Work type:Doctoral dissertation (mb31)
Typology:2.08 - Doctoral Dissertation
Organization:FNM - Faculty of Natural Sciences and Mathematics
Abstract:Doktorska disertacija obravnava nekatere rezultate na grafovskih produktih. V uvodu bomo na kratko predstavili vsebino doktorske disertacije in ponovili nekatere osnovne pojme teorije grafov, ki jih bomo uporabljali v nadaljevanju. Prva tema, ki jo bomo predstavili so neodvisne množice v direktnem produktu. Govorili bomo o velikosti in strukturi največjih neodvisnih množic v direktnem produktu. Najprej bomo predstavili pomembnejše znane rezultate, nato pa bomo pokazali, da ima direkten produkt lihe poti in poljubnega grafa, ter direkten produkt sodega cikla in poljubnega grafa največjo neodvisno množico, ki je unija dveh pravokotnikov. Ugotovili bomo, da obstajajo v direktnem produktu sode poti in poljubnega grafa največje neodvisne množice, ki so lahko tudi drugačne oblike ter zapisali natančno karakterizacijo teh največjih neodvisnih množic. Zapisali bomo zadostni pogoji za drevesa, da ima direkten produkt drevesa in poljubnega grafa največjo neodvisno množico oblike dveh pravokotnikov. V nadaljevanju bomo raziskali posplošeno 3-povezanost v kartezičnem produktu grafov. Prikazali bomo več naravnih načinov, kako dobiti 3-presečno množico S, pri kateri nam graf razpade na vsaj tri komponente. Nato bomo dokazali, da je eden izmed teh načinov vedno optimalen, če sta G in H 2-povezana grafa na vsaj šestih vozliščih. Tako dobimo natančno vrednost posplošene 3-povezanosti kartezičnega produkta dveh 2-povezanih grafov na vsaj šestih vozliščih. Na koncu se bomo ukvarjali z vprašanjem o zgornji meji najmanjšega diametra krepko orientiranega krepkega produkta. Določili bomo natančno vrednost najmanjšega diametra krepkega produkta dveh poti.
Keywords:direktni produkt, kartezični produkt, krepki produkt, neodvisna množica, povezanost, posplošena povezanost, diameter, krepka orientacija
Year of publishing:2018
Publisher:T. Paj Erker]
Source:[Maribor
UDC:519.171(043.3)
COBISS_ID:297733120 New window
NUK URN:URN:SI:UM:DK:D9ISO1AH
Views:673
Downloads:73
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.

Licences

License:CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
Link:http://creativecommons.org/licenses/by-nc-nd/4.0/
Description:The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.
Licensing start date:11.06.2018

Secondary language

Language:English
Title:Some results on connectivity and independent sets in product graphs
Abstract:We study the independence number of direct products of graphs, and the structure of maximum independent sets in them. We prove that every product of an odd path or an even cycle with an arbitrary graph has a maximum independent set which is a union of two rectangles. We show that for an even path, might have independent sets that are not equal to an union of two rectangles, and give a characterization of such maximum independent sets. In the sequel we study the generalized k-connectivity of Cartesian products of graphs. We show several natural ways how to split a graph into three connected components by the removal of vertices. We determine the minimum cardinality of a vertex 3-cut in G□H for any 2-connected graphs G and H on at least six vertices. For graphs G and H we find an upper bound for the minimum diameter of a strong orientation of G⊠H. We prove that Pm⊠Pn admits an optimal orientation for m,n>=5, m≠n. This is a strong orientation, such that the diameter of the directed graph.
Keywords:direct product, Cartesian product, strong product, independent set, connectivity, generalized connectivity, diameter, strong orientation


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