451 KB50 KB112 KB3 KB200820252023He, XinZhang, Hepingštevilka:2letnik:23P2.09 (20 str.)DOI:10.26493/1855-3974.2706.3c8COBISSID_HOST:151964675ISSN:1855-3966URN:URN:NBN:SI:doc-4YW9ILECenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaciklomatsko številocomplete forcing numbercyclomatic numbercylinderglobal forcing numberglobalno določitveno številokoloperfect matchingpolno določitveno številopopolno prirejanjevaljwheelComplete forcing numbers of graphs|The complete forcing number of a graph ?$G$? with a perfect matching is the minimum cardinality of an edge set of ?$G$? on which the restriction of each perfect matching ?$M$? is a forcing set of ?$M$?. This concept can be view as a strengthening of the concept of global forcing number of ?$G$?. T. Došlić J. Math. Chem. 41, No. 3, 217-229 (2007) has obtained that the global forcing number of a connected graph is at most its cyclomatic number. Motivated from this result, we obtain that the complete forcing number of a graph is no more than ?$2$? times its cyclomatic number and characterize the matching covered graphs whose complete forcing numbers attain this upper bound and minus one, respectively. Besides, we present a method of constructing a complete forcing set of a graph. By using such method, we give closed formulas for the complete forcing numbers of wheels and cylindersPolno 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 valjevTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije