Original Research Article

Article volume = 2022 and issue = 2

Pages: 191–194

Article publication Date: November 21, 2022

You can download PDF file of the article here: Download

Visited 226 times and downloaded 135 times

Efficient Dominating Set in Fullerene Graph

Fatemeh Mirzaei(a) and Afshin Behmaram(b)

(a) Master of Graph theory, faculty of mathematical sciences, university of Tabriz, Tabriz, Iran.

(b) Assistant professor, faculty of mathematical sciences, university of Tabriz, Tabriz, Iran.


A Fullerene graph is a 3-regular, 3-connected graph such that all of the Faces is pentagonal and hexagonal.A spanning subgraph of a graph G is called a perfect star packing in G if every component of the spanning subgraph G isomorphic with star graph $K_{1,3}$. The set of Efficient dominating set of the graph G are sets of vertices D such that each vertex in $V(G)-D$ is adjacent to exactly one vertex in D. We prove that the 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 $\dfrac{n}{4}$. Then we show that the size of fullerene graph with an efficient dominating set is 8n.


perfect star packing, fullerene, dominating set.

  • [1] Behmaram, A., Došlić, T. & Friedland, S. Matchings in m-generalized fullerene graphs. Ars Mathematica Contemporanea. 11, 301-313 (2015)
  • [2] Shi, L. The fullerenes with a perfect star packing. (arXiv,2021), https://arxiv.org/abs/2103.11304
  • [3] Shi, L. The fullerene graphs with a perfect star packing. Ars Mathematica Contemporanea. (2022,3)
  • [4] Doslic, T., Taheri dehkordi, M. & Fath-Tabar, G. Packing stars in fullerenes. (2020,9)
  • [5] Gyula , Y.katona . centrosymmetric graphs and a lower bound for graph energy of fullerenes. discussiones mathematicae graph theory 34(2014) 751-768
Cite this article as:
  • Fatemeh Mirzaei and Afshin Behmaram, Efficient Dominating Set in Fullerene Graph, Communications in Combinatorics, Cryptography & Computer Science, 2022(2), PP.191–194, 2022
  • Export citation to BibTeX