Complete Forcing Numbers of Polyphenyl Systems

ايده " نفوذ(اجبار)" مدت زيادي در بسياري از شاخه‌هاي تحقيقاتي وجود داشته است، مانند: رنگ‌آميزي، جهت‌گيري، كمترين فاصله و مجموعه‌هاي غالب در نظريه گراف، كه به همان خوبي مربع‌هاي لاتين، طراحي‌هاي بلوك و سيستم‌هاي استينر در تركيبيات مي‌باشد. اخيرا بحث نفوذ روي جورسازي‌هاي كامل توجه بسياري از محققان را به خود جلب كرده است. يك مجموعه اجباري از يك جورسازي كامل گراف G ، زيرمجموعه‌اي از M است كه در هيچ جورسازيG مشمول نباشد. يك مجموعه اجباري سراسري G كه توسط واكيسويچ و ديگران معرفي شد، يك زير مجموعه از E(G) با محدوديت‌هاي ذاتي كه براي هر دو جورسازي مختلفG وجود دارد، است. با تركيب ايده‌هاي" اجباري" و "سراسري" يك مجموعه، زو و ديگران يك مجموعه اجباري كامل ازG را كه به صورت زير مجموعه‌اي از E(G) با محدوديت‌هايي كه براي هر جورسازي كامل M از Gتعريف مي‌شود، معرفي كردند. مينيمم كاردينال مجموعه‌هاي اجباري كامل، تعداد اجبارهاي كامل G است. در اين مقاله بيان صريحي براي عدد اجباري كامل براي چندين دسته از سيستم‌هاي پلي‌فنيل ارايه مي‌كنيم.

The idea of “forcing” has long been used in many research fields, such as colorings, orientations, geodetics and dominating sets in graph theory, as well as Latin squares, block designs and Steiner systems in combinatorics [D. Donovan, E. S. Mahmoodian, C. Ramsay, A. P. Street, Defining sets in combinatorics: A survey, in: C. D. Wensley (Ed.), Surveys in Combinatorics, Cambridge Univ. Press, 2003, pp. 115?174]. Recently, the forcing on perfect matchings has been attracting more researchers’ attention. A forcing set of a perfect matching M of a graph G is a subset of M contained in no other perfect matchings of G. A global forcing set of G, introduced by Vuki?evi? et al., is a subset of E(G) on which there are distinct restrictions of any two different perfect matchings of G. Combining the above “forcing” and “global” ideas. Xu et al. in [Complete forcing numbers of catacondensed benzenoid, J. Combin. Optim. 29 (2015) 803?814.] introduced a complete forcing set of G defined as a subset of E(G) on which the restriction of any perfect matching M of G is a forcing set of M. The minimum cardinality of complete forcing sets is the complete forcing number of G. In this paper, we give the explicit expressions for the complete forcing number of several classes of polyphenyl systems.