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.

Pravice

URN

URN:NBN:SI:DOC-4YW9ILEC

COBISSID

151964675

DOI

10.26493/1855-3974.2706.3c8

Objavljeno

02.10.2023

Metapodatki

Citiranje

APA:

He, Xin, Zhang, Heping (2023). Complete forcing numbers of graphs. Ars mathematica contemporanea, letnik 23, številka 2, P2.09 (20 str.). URN:NBN:SI:DOC-4YW9ILEC from http://www.dlib.si

MLA:

He, Xin, Zhang, Heping. "Complete forcing numbers of graphs." Ars mathematica contemporanea letnik 23. številka 2 (2023) P2.09 (20 str.).
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-4YW9ILEC>

Ars mathematica contemporanea
2008-
(Zbirni zapis)