3090 KB111 KB200820252019Cavers, MichaelSeyffarth, Karenletnik:17številka:2str. 653-698ISSN:1855-3966COBISSID_HOST:18976857URN:URN:NBN:SI:doc-MTYTYNX7enUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporanea2-drevesa2-treesbarvanje grafagraph colouringGray codesGrayeve kodeHamilton cycleshamiltonski ciklireconfiguration problemsrekonfiguracijski problemiReconfiguring vertex colourings of 2-trees|Let ?$H$? be a graph and let ?$k \geq \chi (H)$? be an integer. The ?$k$?-colouring graph of ?$H$?, denoted ?$G_k(H)$?, is the graph whose vertex set consists of all proper ?$k$?-vertex-colourings (or simply ?$k$?-colourings) of ?$H$? using colours ?$\{1, 2, \dots, k\}$?; two vertices of ?$G_k(H)$? are adjacent if and only if the corresponding ?$k$?-colourings differ in colour on exactly one vertex of ?$H$?. If ?$G_k(H)$? has a Hamilton cycle, then ?$H$? is said to have a Gray code of ?$k$?-colourings, and the Gray code number of ?$H$? is the least integer ?$k_0(H)$? such that ?$G_k(H)$? has a Gray code of ?$k$?-colourings for all ?$k \geq k_0(H)$?. K. Choo and G. MacGillivray determine the Gray code numbers of trees. We extend this result to 2-trees. A 2-tree is constructed recursively by starting with a complete graph on three vertices and connecting each new vertex to an existing clique on two vertices. We prove that if ?$H$? is a 2-tree, then ?$k_0(H) = 4$? unless ?$H$? is isomorphic to the join of a tree ?$T$? and a vertex ?$u$?, where ?$T$? is a star on at least three vertices, or the bipartition of ?$T$? has two even parts; in these cases, ?$k_0(H) = 5$?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$?TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije