Properties, proved and conjectured, of Keller, Mycielski, and queen graphs

angleški

2017

letnik 13, številka 2

barvanje povezav   grafi Mycielskega   Kellerjevi grafi   kraljičini grafi

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Dokažemo več rezultatov o treh družinah grafov. Za kraljičine grafe, definirane z običajnimi premiki šahovske kraljice, najdemo povezavno barvno število v skoraj vseh primerih. Za nedokazani primer imamo domnevo, podprto z ogromno količino izračunov, ki je zahtevala razvoj novega algoritma za barvanje povezav. Domneva pravi, da je povezavno kromatsko število enako maksimalni stopnji, razen kadar mora biti zaradi enostavne aritmetike povezavno barvno število za eno večje od maksimalne stopnje. Za grafe Mycielskega izboljšamo stari rezultat, po katerem so ti grafi hamiltonski in pokažemo, da so hamiltonsko povezani (z izjemo ?$M_3$?, ki je cikel). Za Kellerjeve grafe ?$G_d$? dobimo, v vseh primerih, natančne vrednosti barvnega števila, povezavno barvnega števila, in neodvisnostnega števila; dobimo tudi število pokritja klik v vseh primerih razen za ?$5 \leq d \leq 7$?. Raziskujemo tudi hamiltonske razstavitve Kellerjevih grafov, in jih dobimo vse do ?$G_6$?.

29.05.2020