402 KB42 KB141 KB3 KB200820252023Shi, Lingjuanštevilka:1letnik:23P1.05 (16 str.)DOI:10.26493/1855-3974.2631.be0COBISSID_HOST:143830019ISSN:1855-3966URN:URN:NBN:SI:doc-3TUCUIG9enUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaefficient dominating setfulerenski graffullerene graphperfect star packingpopolno zvezdno pakiranjeučinkovita dominantna množicaThe fullerene graphs with a perfect star packing|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 ?$K_{1,3}$?. For an independent set ?$D \subseteq V(G)$?, if each vertex in ?$V(G) \setminus 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 T. Došlić et al. J. Math. Chem. 58, No. 10, 2223-2244 (2020) and list some subgraphs that preclude the existence of a perfect star packing of type ?$P0$?Fulerenski graf ?$G$? je povezan ravninski kubični graf s samimi peterokotnimi in šesterokotnimi 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 ?$K_{1,3}$?. Neodvisna množica ?$D \subseteq V(G)$?, v kateri ima vsako vozlišče iz ?$V(G) \setminus D$? natanko enega soseda v ?$D$?, se imenuje učinkovita dominantna množica grafa ?$G$?. V tem 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. J. Math. Chem. 58, No. 10, 2223-2244 (2020) in prikažemo nekatere podgrafe, ki izključujejo obstoj popolnega zvezdnega pakiranja tipa ?$P0$?TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije