نتایجی در مجموعه‌های احاطه‌گر دو به دو‌‌‌بیرونی تام در گراف‌ها

الموضوعات :

اکرم محمودی ¹ , علیرضا نجفی زاده ²

1 - گروه ریاضی، دانشگاه پیام نور، تهران، ایران
2 - گروه ریاضی، دانشگاه پیام نور، تهران، ایران

تاريخ الإرسال : 09 الثلاثاء , ذو القعدة, 1441 تاريخ التأكيد : 12 الخميس , صفر, 1444 تاريخ الإصدار : 18 الإثنين , شعبان, 1443

الکلمات المفتاحية: Matching, Total dominating, Dominating, Girth,

ملخص المقالة :

فرض کنید گرافی ساده با مجموعه رئوس و مجموعه یال‌های باشد. مجموعه احاطه‌گر دو به دو- بیرونی از یک مجموعه احاطه‌گری از است به‌طوری که زیرگراف القایی روی دارای تطابق کامل باشد. مینیمم کاردینال مجموعه‌های احاطه‌گر دو به دو-بیرونی را عدد احاطه‌‌ای دو به دو-بیرونی گویند و با نماد نمایش می‌دهند. هم‌چنین، فرض کنید یک مجموعه احاطه‌گر تام از باشد به‌طوری که زیرگراف القایی روی دارای تطابق کامل باشد، در این صورت، را مجموعه احاطه‌گر دو به دو-بیرونی تام گویند. مینیمم کاردینال مجموعه‌های احاطه‌گر دو به دو-بیرونی تام را عدد احاطه‌‌ای دو به دو-بیرونی تام گویند و با نماد نمایش می‌دهند. در این مقاله ضمن معرفی این مفهوم، به مطالعه روی برخی خواص اساسی این پارامتر از گراف پرداخته و کرا‌ن‌هایی بر حسب مرتبه، اندازه، کمرگراف و ... برای آن ارائه می‌شود. همچنین، نامساوی معروف نورس- گادم برای گراف‌های منظم ارائه می‌گردد.

المصادر:

 [1] H. A. Ahangar, M. Chellali, D. Kuziak, and V. Samodivkin, Connected graphs with maximal Roman domination numbers one less than their order n, Ars Combinatoria, 144 (2019) 207-224.

 

[2] M. H. Akhbari, R. Hasni, O. Favaron, H. Karami, and S.M. Sheikholeslami, On the outer-connected domination in graphs, Journal of Combinatorial Optimization, 26 (2013) 10-18.

 

[3] R. B. Allan and R.C. Laskar, On domination and independent domination numbers of a graph, Discrete Mathematics, 23 (1978) 73-76.

 

 [4] M. Atapour and N. Soltankhah, On total dominating sets in graphs, Int. J. Contemp. Math. Sciences, 4 (2009) 253-257.

 

 [5] P. Azizi Keshavarz and A. Tehranian, Incidence dominating numbers of graphs, Journal of New Researches in Mathematics, 6(24) (2020) 85-96.

[6] B. Brešar, M. A. Henning and D.F. Rall, Rainbow domination in graphs, Taiwanese Journal of Mathematics, 12 (2008) 213-225.

 

[7] B. Brešar and T.K. Šumenjak, On the 2- rainbow domination in graphs, Discrete Applied Mathematics 155 (2007) 2394-2400.

 

[8] E. J. Cockayne, R.M. Dawes and S. T. Hedetniemi, Total domination in graphs,  Networks 10 (1980) 211-219.

 

[9] T. W. Haynes and P. J. Slater, Paired domination in graphs, Networks 32 (1998) 199-206.

 

[10] M. kamali Pashakalai, H. A. Ahangar, M. Motiei and S. M. Sheikholeslami,  Results on the maximal Roman domination number in graphs, Journal of New Researches in Mathematics, 6 (25) (2020) 197-208.

[11] Ch. Y. Lin, J. J. Liu, Y. L. Wang and Ch. Ch. Hsu, Dominating sets with matching outside, The 32^nd workshop on Combinatorial Mathematics and Computation Theory.

[12] A. Mahmoodi, L. Asgharsharghi, Outer-paired domination in graphs, Discrete Mathematics, Algorithms and Applications 12(6), 2050072 (2020).

[13] H. Rahbani, S. N. Doosti Motlagh and N. Jafari Rad, New bounds on weak odd dominating set in trees, Journal of New Researches in Mathematics, (2021).