395 KB40 KB200820252019Brinkmann, GunnarOzeki, KentaVan Cleemput, Nicoštevilka:1letnik:17str. 51-66ISSN:1855-3966COBISSID_HOST:18912089URN:URN:NBN:SI:doc-0N1UURJ6enUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporanea3-sprehod3-walkdominacijadominationgrafgraphHamiltonian cyclehamiltonski cikelTypes of triangle in Hamiltonian triangulations and an application to domination and k-walks|We investigate the minimum number ?$t_0(G)$? of faces in a Hamiltonian triangulation ?$G$? so that any Hamiltonian cycle ?$C$? of ?$G$? has at least ?$t_0(G)$? faces that do not contain an edge of ?$C$?. We prove upper and lower bounds on the maximum of these numbers for all triangulations with a fixed number of facial triangles. Such triangles play an important role when Hamiltonian cycles in triangulations with 3-cuts are constructed from smaller Hamiltonian cycles of 4-connected subgraphs. We also present results linking the number of these triangles to the length of 3-walks in a class of triangulation and to the domination numberRaziskujemo število ?$t_0(G)$?, tj. minimalno število lic v neki hamiltonski triangulaciji ?$G$?, tako da ima vsak hamiltonski cikel ?$C$? v ?$G$? vsaj ?$t_0(G)$? lic, ki ne vsebujejo povezave iz ?$C$?. Dokažemo zgornje in spodnje meje za maksimum teh števil za vse triangulacije s fiksnim številom trikotniških lic. Takšni trikotniki igrajo pomembno vlogo, ko v triangulacijah s 3-prerezi konstruiramo hamiltonski cikel iz manjših hamiltonskih ciklov 4-povezanih podgrafov. Predstavimo tudi rezultate, ki povezujejo število teh trikotnikov z dolžino 3-sprehodov v razredu triangulacij in z dominacijskim številomTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije