The fullerenes with a perfect star packing

Ling-Juan Shi

Published 2021-03-21Version 1

A spanning subgraph of a graph $G$ is called a perfect star packing in $G$ if every component of the spanning subgraph is isomorphic to the star graph $K_{1,3}$. An efficient dominating set of graph $G$ is a vertex subset $D$ of $G$ such that each vertex of $G$ not in $D$ is adjacent to exactly one vertex from $D$ and any two vertices of $D$ are not adjacent in $G$. Fullerene graph is a connected plane cubic graph with only pentagonal and hexagonal faces, which is the molecular graph of carbon fullerene. Clearly, a perfect star packing in a fullerene graph $G$ on $n$ vertices will exist if and only if $G$ has an efficient dominating set of cardinality $\frac{n}{4}$. The problem of finding an efficient dominating set is algorithmically hard \cite{Alg_hard}. In this paper, we give a characterization for a fullerene graph to own a perfect star packing. And mainly show that it is necessary for a fullerene $G$ owning a perfect star packing to have order being divisible by $8$. This answers an open problem asked by Dosli\'{c} et. al. and also shows that a fullerene graph with an efficient dominating set has $8n$ vertices. By the way, we find some counterexamples for the necessity of Theorem $14$ in \cite{Doslic} and list some forbidden configurations to preclude the existence of a perfect star packing of type $P0$.