339 KB44 KB150 KB3 KB200820262026Bickle, AllanBrinkmann, Gunnarštevilka:1, article p1.03letnik:26str. 1-15DOI:10.26493/1855-3974.3066.5bfISSN:1855-3974COBISSID_HOST:288315907URN:URN:NBN:SI:doc-18MFNMNAenUniverza na PrimorskemArs mathematica contemporanea2-drevo2-treeHamiltonian cyclehamiltonski cikeltriangulacijatriangulationYutsis partitionYutsisova particijaPlane triangulations without large 2-trees|In 1995 Leizhen Cai asked whether each plane triangulation has a spanning 2-tree. This question was recently answered in the negative by Bickle. He gave a plane triangulation on 38 vertices for which each 2-tree contained in it misses at least one vertex. We give a smaller example on 29 vertices and show that for each c>0 there are plane triangulations P=(V,E), so that each 2-tree that is a subgraph of P contains fewer than c|V| vertices. We also give a lower bound for the size of a maximum 2-tree in plane triangulations by proving that each plane triangulation P=(V,E) contains a 2-tree on at least log_2 (|V|-1)+4 -log_2 3 vertices. Finally we give structural criteria based on the decomposition trees of Jackson and Yu that guarantee the existence of spanning 2-trees in plane triangulations. The results are proven by using the close relation of 2-trees to hamiltonian cycles and to induced trees in the dual for plane triangulations without separating trianglesLeta 1995 je Leizhen Cai vprašal, ali ima vsaka ravninska triangulacija razpenjajoče se 2-drevo. Na to vprašanje je nedavno negativno odgovoril Bickle. Podal je ravninsko triangulacijo s 38 vozlišči, za katero vsako 2-drevo, ki je vsebovano v njej, izpusti vsaj eno vozlišče. Mi podamo manjši primer s 29 vozlišči in pokažemo, da za vsako c > 0 obstajajo ravninske triangulacije P = (V, E), tako da vsako 2-drevo, ki je podgraf P , vsebuje manj kot c|V | vozlišč. Podamo tudi spodnjo mejo za velikost največjega 2-drevesa v ravninskih triangulacijah, tako da dokažemo, da vsaka ravninska triangulacija P = (V, E) vsebuje 2-drevo z vsaj log2(|V | - 1) + 4 - log2 3 vozlišči. Nazadnje podamo strukturna merila, ki temeljijo na dekompozicijskih drevesih Jacksona in Yuja, in zagotavljajo obstoj razpenjajočih se 2-dreves v ravninskih triangulacijah. Rezultati so dokazani z uporabo tesne povezave med 2-drevesi, hamiltonskimi cikli in induciranimi drevesi v dualu za ravninske triangulacije brez ločevalnih trikotnikovTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije