The fullerene graphs with a perfect star packing

angleški

2023

letnik 23, številka 1

fulerenski graf   popolno zvezdno pakiranje   učinkovita dominantna množica

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

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$?.

02.10.2023