On the anti-forcing number of graph powers

Document Type : Original paper

Authors

Department of Mathematical Sciences, Yazd University, 89195-741, Yazd, Iran

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)$.     For every $m\in\mathbb{N}$, the $m$th power of $G$, denoted by $G^m$, is a graph with the same vertex set as $G$ such that two vertices are adjacent in $G^m$ if and only if their distance is at most $m$ in $G$. In this paper, we study the anti-forcing number of the powers of some graphs.

Keywords

Main Subjects

References

[1] G. Agnarsson and M.M. Halld´orsson, Coloring powers of planar graphs, SIAM J. Discrete Math. 16 (2003), no. 4, 651–662.
https://doi.org/10.1137/S0895480100367950
[2] S. Alikhani, S. Jahari, M. Mehryar, and R. Hasni, Counting the number of dominating sets of cactus chains, Optoelectron. Adv. Mater. Rapid Commun. 8 (2014), no. 9-10, 955–960.
[3] S. Alikhani and N. Soltani, Anti-forcing number of some specific graphs, Iran. J. Math. Chem. 8 (2017), no. 3, 313–325.
https://doi.org/10.22052/ijmc.2017.60978.1235
[4] S. Alikhani and S. Soltani, Distinguishing number and distinguishing index of natural and fractional powers of graphs, Bull. Iran. Math. Soc. 43 (2017), no. 7, 2471–2482.
[5] X. An and B. Wu, The Wiener index of the kth power of a graph, Appl. Math. Lett. 21 (2008), no. 5, 436–440.
https://doi.org/10.1016/j.aml.2007.03.025
[6] Z. Che and Z. Chen, Forcing on perfect matchings-A survey, MATCH Commun. Math. Comput. Chem. 66 (2011), no. 1, 93–136.
[7] F. Harary, D.J. Klein, and T.P. Živkovič, Graphical properties of polyhexes: perfect matching vector and forcing, J. Math. Chem. 6 (1991), no. 1, 295–306.
https://doi.org/10.1007/BF01192587
[8] A.M. Hobbs, Some hamiltonian results in powers of graphs, J. Res. Nat. Bur. Standards Sect. B 77 (1973), no. 1-2, 1–10.
[9] D.J. Klein and M. Randić, Innate degree of freedom of a graph, J. Comput. Chem. 8 (1987), no. 4, 516–521.
https://doi.org/10.1002/jcc.540080432
[10] D. Král’, Coloring powers of chordal graphs, SIAM J. Discrete Math. 18 (2004), no. 3, 451–461.
https://doi.org/10.1137/S0895480103424079
[11] H. Lei, Y.N. Yeh, and H. Zhang, Anti-forcing numbers of perfect matchings of graphs, Discrete Appl. Math. 202 (2016), 95–105.
https://doi.org/10.1016/j.dam.2015.08.024
[12] L. Lovász and M.D. Plummer, Matching Theory, Ann. Discrete Math., North-Holland, Amsterdam, 1986.
[13] M. Randić and D.J. Klein, Mathematical and computational concepts in chemistry, Mathematical and Computational Concepts in Chemistry, John Wiley & Sons, New York (1985), 274–282.
[14] D. Vukičević and N. Trinajstić, On the anti-Kekul´e number and anti-forcing number of cata-condensed benzenoids, J. Math. Chem. 43 (2008), no. 2, 719–726.
https://doi.org/10.1007/s10910-006-9223-5
[15] D. Vukičević  and N. Trinajstić, On the anti-forcing number of benzenoids, J. Math. Chem. 42 (2007), no. 3, 575–583.
https://doi.org/10.1007/s10910-006-9133-6
[16] Q. Yang, H. Zhang, and Y. Lin, On the anti-forcing number of fullerene graphs, MATCH Commun. Math. Comput. Chem. 74 (2015), no. 3, 673–692.
[17] H. Zhang, D. Ye, and W.C. Shiu, Forcing matching numbers of fullerene graphs, Discrete Appl. Math. 158 (2010), no. 5, 573–582.
https://doi.org/10.1016/j.dam.2009.10.013
Communications in Combinatorics and Optimization
Volume 9, Issue 3
September 2024
Pages 497-507

Files

Share

How to cite

Statistics