Anti-forcing Number of Some Specific Graphs

Document Type : Research Paper

Authors

1 Yazd University, Yazd, Iran

2 Yazd University

Abstract

Let $G=(V,E)$ be a simple connected graph. A perfect matching (or Kekul'e structure in chemical literature) of $G$ is a set of disjoint edges which covers all vertices of $G$. The anti-forcing number of $G$ is the smallest number of edges such that the remaining graph obtained by deleting these edges has a unique perfect matching and is denoted by $af(G)$. In this paper we consider some specific graphs that are of importance in chemistry and study
their anti-forcing numbers.

Keywords

Main Subjects


1. S. Alikhani, S. Jahari, M. Mehryar and R. Hasni, Counting the number of
dominating sets of cactus chains, Opt. Adv. Materials–Rapid Commun. 8 (9–10)
(2014) 955–960.
2. S. Alikhani, R. Hasni, and G. C. Lau, Bounds for energy of certain polyphenylene
dendrimers, J. Comput. Theor. Nanosci. 9 (2012) 1055–1058.
3. E. Deutsch and S. Klavžar, Computing the Hosoya polynomial of graphs from
primary subgraphs, MATCH Commun. Math. Comput. Chem. 70 (2013) 627–644.
4. J. A. Gallian, Dynamic survey DS6: graph labeling, Elec. J. Combin. DS6 1–58
(2007).
5. F. Harary, D. J. Klein and T. P. Zivković, Graphical properties of polyhexes:
perfect matching vector and forcing, J. Math. Chem. 6 (1991) 295–306.
6. D. J. Klein and M. Randić, Innate degree of freedom of a graph, J. Comput. Chem.
8 (1987) 516–521.
7. H. Lei, Y. N. Yeh, and H. Zhang, Anti–forcing numbers of perfect matchings of
graphs, Discrete Appl. Math. 202 (2016) 95–105.
8. L. Lovász, M.D. Plummer, Matching Theory, North–Holland, Amsterdam, 1986.
9. D. Vukičević and N. Trinajstić, On the anti–forcing number of benzenoids. J.
Math. Chem. 42 (2007) 575–583.
10. D. Vukičević and N. Trinajstić, On the anti–Kekulé number and anti–forcing
number of cata–condensed benzenoids, J. Math. Chem. 43 (2008) 719–726.
11. H. Zhang, D. Ye and W. Shiu, Forcing matching numbers of fullerene graphs,
Discrete Appl. Math. 158 (2010) 573–582.