Direktni produkti polnih grafov

doktorska disertacija

Gašper Mekiš (Author), Sandi Klavžar (Mentor)

Abstract

Prvi del disertacije je posvečen neodvisnim dominantnim množicam direktnega produkta štirih polnih grafov. Eksplicitno so opisane T1-množice, tj. množice, kjer se poljubni par vozlišč ujema na natanko enem mestu. Glavni rezultat tega dela reče, da direktni produkt štirih polnih grafov premore idomatsko particijo na T1-množice natanko tedaj, ko sta reda vsaj dveh faktorjev deljiva s 3. V nadaljevanju postane osrednja tema dominantno in polno dominantno število direktnega produkta končno mnogo polnih grafov. Za slednje grafe je podana spodnja meja, ki je točna, če so faktorji dovolj veliki v primerjavi s številom faktorjev. Najsplošnejši rezultat tega dela je spodnja meja za dominantno (in polno dominantno) število direktnega produkta poljubnih dveh grafov, ki je izražena z dominatnima številoma faktorjev. Opisane so neskončne družine grafov, ki zavzamejo enakost. Zadnji del je posvečen mavrični povezanosti direktnega produkta. Podana je zgornja meja za mavrično povezanost direktnega produkta dveh grafov v odvisnosti od mavrične povezanosti faktorjev in še dveh podobnih invariant dobljenih s pomočjo lihih ciklov. Izkaže se, da so ravno polni grafi izjema omenjene meje. Za produkt dveh polnih grafov je dana točna vrednost (krepke) mavrične povezanosti. Kot dodatek so na koncu podani tudi nekateri rezultati glede ostalih treh standardnih grafovskih produktov.

Keywords

grafovski produkti;dominantna množica;dominantno število;idomatska particija;mavrična povezanost;disertacije;

Data

Language:	Slovenian
Year of publishing:	2013
Source:	[Maribor
Typology:	2.08 - Doctoral Dissertation
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	G. Mekiš]
UDC:	519.17(043.3)
COBISS:	19790856
Views:	2273
Downloads:	148
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Direct products of complete graphs
Secondary abstract:	In the first part of this thesis independent dominating sets in the direct product of four complete graphs are considered. Possible types of such sets are classified. The sets in which every pair of vertices agree in exactly one coordinate, called T1-sets, are explicitly described. It is proved that the direct product of four complete graphs admits an idomatic partition into T1-sets if and only if each factor has at least three vertices and the orders of at least two factors are divisible by 3. Next attention is focused on the domination number and the total domination number of the direct product of finitely many complete graphs. For this graphs a sharp lower bound is given. Sharpness is established in the case when the factors are large enough in comparison to the number of factors. The main result of this part gives a lower bound for the domination (and the total domination) number of the direct product of two arbitrary graphs. This bound is given in terms of domination numbers of the factors. Infinite families of graphs that attain the bound are presented. Some additional parallels with the total domination number are made. In the last part an upper bound for the rainbow connection number of the direct product of two graphs is given in terms of rainbow connection number of the factors and two similar invariants obtained with help of odd cycles. As it turns out, complete graphs form an exception for the bound. To fill the gap, an exact value of the (strong) rainbow connection number for products of two complete graphs is provided. As an extra, at the end some results concerning the remaining three standard graph products are given.
Secondary keywords:	graph products;dominating set;domination number;idomatic partition;rainbow connection;dissertations;
URN:	URN:SI:UM:
Type (COBISS):	Dissertation
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	VII, 74 str.
Keywords (UDC):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;combinatorial analysis;graph theory;kombinatorika;
ID:	81750