Complete forcing numbers of graphs - He, Xin (Ars mathematica contemporanea, 2023)
Polno določitveno število grafa ?$G$? s popolnim prirejanjem je minimalna moč množice povezav grafa ?$G$?, za katero je zožitev vsakega popolnega prirejanja ?$M$? določitvena množica za ?$M$?. Ta koncept lahko gledamo kot nadgradnjo koncepta globalnega določitvenega števila grafa ?$G$?. Došlić je leta 2007 dokazal, da je globalno določitveno število povezanega grafa manjše ali kvečjemu enako njegovemu ciklomatskemu številu. Motivirani s tem rezultatom pokažemo, da polno določitveno število grafa ni večje od 2-kratnika njegovega ciklomatskega števila, in karakteriziramo s prirejanji pokrite grafe, katerih polno določitveno število doseže to zgornjo mejo, oziroma je za ena manjše. Predstavimo tudi metodo konstruiranja polne določitvene množice grafa. S pomočjo te metode izpeljemo sklenjene formule za polna določitvena števila koles in valjev.
Keywords: ciklomatsko število; complete forcing number; cyclomatic number; cylinder; global forcing number; globalno določitveno število; kolo; perfect matching; polno določitveno število; popolno prirejanje; valj; wheel