Reconfiguring vertex colourings of 2-trees

angleški

2019

letnik 17, številka 2

2-drevesa   barvanje grafa   Grayeve kode   hamiltonski cikli   rekonfiguracijski problemi

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

Naj bo ?$H$? graf in naj bo ?$k \geq \chi (H)$? celo število. Graf ?$k?$-barvanj grafa ?$H$?, označen z ?$G_k(H)$?, je graf, katerega množica vozlišč sestoji iz vseh pravih ?$k$?-vozliščnih barvanj (ali preprosto ?$k$?-barvanj) grafa ?$H$? z barvami ?$\{1, 2, \dots, k\}$?; vozlišči grafa ?$G_k(H)$? sta sosednji, če in samočce se ustrezni ?$k$?-barvanji razlikujeta v barvi natanko enega vozlišča grafa ?$H$?. Če ima ?$G_k(H)$? hamiltonski cikel, potem pravimo, da ima ?$H$? Grayevo kodo iz ?$k$?-barvanj. Najmanjše celo število ?$k_0(H)$?, pri katerem ima ?$G_k(H)$? Grayevo kodo iz ?$k$?-barvanj za vse ?$k \geq k_0(H)$?, imenujemo prag Grayeve kode grafa ?$H$?. Choo in MacGillivray sta določila pragove Grayevih kod za drevesa. V pričujočem članku razširimo ta rezultat na 2-drevesa. Konstrukcija 2-drevesa poteka rekurzivno: začnemo s polnim grafom na treh vozliščih, potem pa vsako novo vozlišče dodamo neki že obstoječi kliki na dveh vozliščih. Dokažemo, da če je ?$H$? 2-drevo, potem je ?$k_0(H) = 4$?, razen če je ?$H$? izomorfen spoju drevesa ?$T$? in vozlišča ?$u$?, kjer je ?$T$? zvezda na najmanj treh vozlišcih, ali če se ?$T$? deli na dva enako velika dela; v teh dveh primerih je ?$k_0(H) = 5$?.

29.05.2020