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

محورهای موضوعی : جبر

اکرم محمودی ¹ (گروه ریاضی، دانشگاه پیام نور، تهران، ایران)
علیرضا نجفی زاده ² (گروه ریاضی، دانشگاه پیام نور، تهران، ایران)

تاریخ دریافت : 1399/04/10 تاریخ پذیرش : 1401/06/17 تاریخ انتشار : 1401/01/01

کلید واژه: Matching, Total dominating, Dominating, Girth,

چکیده مقاله :

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

چکیده انگلیسی:

Let G=(V, E) be a simple graph with vertex set V and edge set E. An outer-paired dominating set D of a graph G is a dominating set such that the subgraph induced by V\D has a perfect matching. The outer-paired domination number of G denoted by is the minimum cardinality of an outer-paired dominating set of G. Moreover, a total outer-paired dominating set D of a graph G is a total dominating set such that the subgraph induced by V\D has a perfect matching. The total outer-paired domination number of G denoted by is the minimum cardinality of a total outer-paired dominating set of G. In this paper, besides introducing such a notion for a graph, we study some fundamental properties of this invariant. Furthermore, we present some bounds in terms of the order, the size, the girth of a graph and etc. Finally, the well-known Nordhaus-Gaddum inequality is obtained for regular graphs.

منابع و مأخذ:

 [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).