Direktni produkti polnih grafov

doktorska disertacija

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

Povzetek

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.

Ključne besede

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

Podatki

Jezik:	Slovenski jezik
Leto izida:	2013
Izvor:	[Maribor
Tipologija:	2.08 - Doktorska disertacija
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	G. Mekiš]
UDK:	519.17(043.3)
COBISS:	19790856
Št. ogledov:	2273
Št. prenosov:	148
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Direct products of complete graphs
Sekundarni povzetek:	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.
Sekundarne ključne besede:	graph products;dominating set;domination number;idomatic partition;rainbow connection;dissertations;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Doktorska disertacija
Komentar na gradivo:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	VII, 74 str.
Ključne besede (UDK):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;combinatorial analysis;graph theory;kombinatorika;
ID:	81750