Types of triangle in Hamiltonian triangulations and an application to domination and k-walks - Brinkmann, Gunnar (Ars mathematica contemporanea, 2019)
Raziskujemo š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 številom.
Keywords: 3-sprehod; 3-walk; dominacija; domination; graf; graph; Hamiltonian cycle; hamiltonski cikel