{
  "id": "2103.11304",
  "version": "v1",
  "published": "2021-03-21T04:51:09.000Z",
  "updated": "2021-03-21T04:51:09.000Z",
  "title": "The fullerenes with a perfect star packing",
  "authors": [
    "Ling-Juan Shi"
  ],
  "comment": "19pages,6figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "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$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-03-21T04:51:09.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "perfect star packing",
      "efficient dominating set",
      "fullerene graph",
      "spanning subgraph",
      "connected plane cubic graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}