2021/03/21 by Lingjuan Shi, Ling-Juan Shi, Shi, Ling-Juan
Chemistry · Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Fullerene Chemistry and Applications #Graph theory and applications #Interconnection Networks and Systems #math.CO
paper · pdf · doi:10.48550/arxiv.2103.11304
19pages,6figures
arxiv created 2021/03/21 · openalex publication_date 2021/03/21 · arxiv updated 2021/03/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 K1,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 (n)/(4). The problem of finding an efficient dominating set is algorithmically hard \citeAlghard. 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ć 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 \citeDoslic and list some forbidden configurations to preclude the existence of a perfect star packing of type P0.