تعداد نشریات | 5 |
تعداد شمارهها | 108 |
تعداد مقالات | 1,228 |
تعداد مشاهده مقاله | 1,148,333 |
تعداد دریافت فایل اصل مقاله | 1,007,657 |
On the anti-forcing number of graph powers | ||
Communications in Combinatorics and Optimization | ||
مقاله 8، دوره 9، شماره 3، آذر 2024، صفحه 497-507 اصل مقاله (3.47 M) | ||
نوع مقاله: Original paper | ||
شناسه دیجیتال (DOI): 10.22049/cco.2023.27874.1378 | ||
نویسندگان | ||
Neda Soltani؛ Saeid Alikhani* | ||
Department of Mathematical Sciences, Yazd University, 89195-741, Yazd, Iran | ||
چکیده | ||
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. | ||
کلیدواژهها | ||
perfect matching؛ anti-forcing number؛ power of a graph | ||
مراجع | ||
[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 | ||
آمار تعداد مشاهده مقاله: 199 تعداد دریافت فایل اصل مقاله: 1,055 |