ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P1.05
https://doi.org/10.26493/1855-3974.2631.be0
(Also available at http://amc-journal.eu)
The fullerene graphs with a perfect star packing*
Lingjuan Shi †
School of Software, Northwestern Polytechnical University,
Xi’an, Shaanxi 710072, P. R. China
Received 15 May 2021, accepted 23 March 2022, published online 29 September 2022
Abstract
Fullerene graph G is a connected plane cubic graph with only pentagonal and hexagonal
faces, which is the molecular graph of carbon fullerene. A spanning subgraph of G is called
a perfect star packing in G if its each component is isomorphic to K1,3. For an independent
set D ⊆ V (G), if each vertex in V (G) \D has exactly one neighbor in D, then D is called
an efficient dominating set of G. In this paper we show that the number of vertices of a
fullerene graph admitting a perfect star packing must be divisible by 8. This answers an
open problem asked by Došlić et al. and also shows that a fullerene graph with an efficient
dominating set has 8n vertices. In addition, we find some counterexamples for the necessity
of Theorem 14 of paper of Došlić et al. from 2020 and list some subgraphs that preclude
the existence of a perfect star packing of type P0.
Keywords: Fullerene graph, perfect star packing, efficient dominating set.
Math. Subj. Class. (2020): 05C70, 05C92
*This work was supported in part by the National Natural Science Foundation of China (grant no. 11901458
and 11871256) and by the Fundamental Research Funds for the Central Universities (grant no. D5000200199).
†The author is very grateful to Wuyang Sun and the anonymous referees for their careful reading and valuable
comments, which greatly improved this paper.
E-mail address: shilj18@nwpu.edu.cn (Lingjuan Shi)
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) #P1.05
https://doi.org/10.26493/1855-3974.2631.be0
(Dostopno tudi na http://amc-journal.eu)
Fulerenski grafi s popolnim pakiranjem zvezd*
Lingjuan Shi †
School of Software, Northwestern Polytechnical University,
Xi’an, Shaanxi 710072, P. R. China
Prejeto 15. maja 2021, sprejeto 23. marca 2022, objavljeno na spletu 29. septembra 2022
Povzetek
Fulerenski graf G je povezan ravninski kubični graf s samimi peterokotnimi in šes-
terokotnimi lici, ki predstavlja molekularni graf ogljikovega fulerena. Vpeti podgraf grafa
G se imenuje popolno zvezdno pakiranje v grafu G, če je vsaka njegova komponenta
izomorfna K1,3. Neodvisna množica D ⊆ V (G), v kateri ima vsako vozlišče iz V (G) \D
natanko enega soseda v D, se imenuje učinkovita dominantna množica grafa G. V tem
članku pokažemo, da mora biti število vozlišč fulerenskega grafa, ki dopušča popolno
zvezdno pakiranje, deljivo z 8. To odgovarja na odprt problem, ki so ga zastavili Došlić in
dr. in kaže, da ima fulerenski graf z učinkovito dominantno množico 8n vozlišč. Pokažemo
tudi nekaj protiprimerov za nujnost izreka 14 v članku Došlić in dr. iz leta 2020 in prikažemo
nekatere podgrafe, ki izključujejo obstoj popolnega zvezdnega pakiranja tipa P0.
Ključne besede: Fulerenski graf, popolno zvezdno pakiranje, učinkovita dominantna množica.
Math. Subj. Class. (2020): 05C70, 05C92
*To delo sta delno podprla National Natural Science Foundation of China (dotaciji št. 11901458 in 11871256)
ter Fundamental Research Funds for the Central Universities (dotacija št. D5000200199).
†Avtor je zelo hvaležen Wuyangu Sunu in recenzentom za skrbno branje in dragocene komentarje, ki so močno
izboljšali ta članek.
E-poštni naslov: shilj18@nwpu.edu.cn (Lingjuan Shi)
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/