ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P2.09
https://doi.org/10.26493/1855-3974.2706.3c8
(Also available at http://amc-journal.eu)
Complete forcing numbers of graphs*
Xin He , Heping Zhang †
School of Mathematics and Statistics, Lanzhou University, Lanzhou,
Gansu 730000, P.R. China
Received 10 October 2021, accepted 30 June 2022, published online 13 December 2022
Abstract
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. Došlić in 2007 obtained that the global forcing number of a con-
nected 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 cylinders.
Keywords: Perfect matching, global forcing number, complete forcing number, cyclomatic number,
wheel, cylinder.
Math. Subj. Class. (2020): 05C70, 05C90, 92E10
*The authors are grateful to anonymous reviewers for their careful reading and valuable suggestions to improve
this manuscript. This work is supported by National Natural Science Foundation of China (Grant No. 11871256
and 12271229).
†Corresponding author.
E-mail addresses: hex2015@lzu.edu.cn (Xin He), zhanghp@lzu.edu.cn (Heping Zhang)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
ISSN 1855-3966 (tiskana izd.), ISSN 1855-3974 (elektronska izd.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P2.09
https://doi.org/10.26493/1855-3974.2706.3c8
(Dostopno tudi na http://amc-journal.eu)
Polna določitvena števila grafov*
Xin He , Heping Zhang †
School of Mathematics and Statistics, Lanzhou University, Lanzhou,
Gansu 730000, P.R. China
Prejeto 10. oktobra 2021, sprejeto 30. junija 2022, objavljeno na spletu 13. decembra 2022
Povzetek
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 rezul-
tatom pokažemo, da polno določitveno število grafa ni večje od 2-kratnika njegovega cik-
lomatskega š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 kon-
struiranja polne določitvene množice grafa. S pomočjo te metode izpeljemo sklenjene for-
mule za polna določitvena števila koles in valjev.
Ključne besede: Popolno prirejanje, globalno določitveno število, polno določitveno število, ciklo-
matsko število, kolo, valj.
Math. Subj. Class. (2020): 05C70, 05C90, 92E10
*Avtorja sta hvaležna neznanim recenzentom za njihovo skrbno branje in dragocene predloge za izboljšavo
tega rokopisa. To raziskavo je podprla National Natural Science Foundation of China (dotaciji št. 11871256 in
12271229).
†Kontaktni avtor.
E-poštna naslova: hex2015@lzu.edu.cn (Xin He), zhanghp@lzu.edu.cn (Heping Zhang)
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/