نتایجی برای عدد احاطه ای رومی ماکسیمال در گراف ها
محورهای موضوعی : آمارمریم کمالی پاشاکلایی 1 , حسین عبداله زاده آهنگر 2 , مهران مطیعی 3 , سید محمود شیخ الاسلامی 4
1 - گروه ریاضی، دانشگاه صنعتی نوشیروانی بابل، بابل، ایران
2 - گروه ریاضی، دانشگاه صنعتی نوشیروانی بابل، بابل، ایران
3 - گروه ریاضی، دانشگاه صنعتی نوشیروانی بابل، بابل، ایران
4 - گروه ریاضی، دانشگاه شهید مدنی آذربایجان، تبریز، ایران
کلید واژه: maximal Roman dominating function, Maximal dominating set, Roman dominating function,
چکیده مقاله :
تابع f:V(G)→{0,1,2} یک تابع احاطه‌گر رومی (RDF) برای گراف G نامیده می‌شود هرگاه هر راس u که f(u )=0 مجاور به یک راس v باشد که f(v )=2. وزن یک RDF f برابر است با w(f)=∑_(v∈V)▒f(v) . عدد احاطه‌گر رومی گراف G را که با نماد γ_R (G) نمایش می‌دهیم کمترین وزن یک RDF در گراف G است. تابع احاطه‌گر رومی ماکسیمال (MRDF) برای گراف G یک تابع احاطه‌گر رومی f=(V_0,V_1,V_2) می‌باشد به طوری که مجموعه‌ی V_0={v∈V(G)|f(v)=0} یک مجموعه‌ی احاطه‌گر برای گراف G نباشد. وزن یک MRDF f برابر است با w(f)=∑_(v∈V)▒f(v) . عدد احاطه‌گر رومی ماکسیمال گراف G را که با نماد γ_mR (G) نمایش می‌دهیم کمترین وزن یک MRDF در گراف G است. در این مقاله مطالعه روی پارامتر احاطه‌گر رومی ماکسیمال را ادامه می‌دهیم. ابتدا تمام گراف‌های G با کمر حداقل 6 را دسته بندی می‌کنیم به طوری که γ_mR (G)=n-2 باشد و سپس ویژگی مورد نظر را برای برخی از گراف‌های با کمر حداکثر 5 بررسی می‌نماییم.
A Roman dominating function on a graph G is a labeling f:V(G)→{0,1,2} such that every vertex with label 0 has a neighbor with label 2. A Roman dominating function on a graph G is a labeling f:V(G)→{0,1,2} such that every vertex with label 0 has a neighbor with label 2. A maximal Roman dominating function on a graph G is a Roman dominating function f such that V_0={w ∈V(G)│f(w)=0} is not a dominating set of G. The weight of maximal Roman dominating function is the value w(f)=f(V(G))=∑_(x∈V(G))▒〖f(x).〗 The maximal Roman dominating number γ_mR (G) of a graph G equals the minimum weight of a maximal Roman dominating function on G. In this paper, we continue the study of maximal Roman domination number. First, we characterize all graphs G of order n with g(G)≥6 for which γ_mR (G) =n-2, and then, we consider this property for some graphs with girth at most 5.
[1] H. Abdollahzadeh Ahangar, A. Bahremandpour, S.M. Sheikholeslami, N.D. Soner, Z. Tahmasbzadehbaee and L. Volkman, Maximal Roman domin-ation numbers in graphs, Util. Math. 103 (2017) 245-258.
[2] H. Abdollahzadeh Ahangar, M. Chellali, D. Kuziak, and V. Samodivkin, On maximal Roman domination in graphs, Int. J. Comput. Math. 93(7) (2016) 1093-1102.
[3] H. Abdollahzadeh Ahangar, M. Chellali, D. Kuziak, and V. Samodivkin, Connected graphs with maximal Roman domination numbers one less than their order, Ars combin. 144 (2019) 207-224.
[4] E.J. Cockayne, P.M. Dreyer Jr., S.M. Hedetniemi, and S.T. Hedetniemi,On Roman domination in graphs, Discrete Math. 278 (2004)11-22.
[5] A. Hansberg, N. Jafari Rad, and L. Volkmann, Vertex and edge critical Roman domination in graphs, Util. Math. 92 (2013) 73-88.
[6] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater (eds), Domination in Graphs: Advanced Topic, Marcel Dekker, Inc. New York, 1998.
[7] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater (eds), Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
[8] V.R. Kulli and B. Janakiram, The maximal domination number of a graph, Graph Theory Notes ofNew York, New York Academy of Sciences XXXIII (1997), 11-13.
[9] V.R. Kulli and B. Janakiram, A note on maximal domination number of a graph, Graph Theory Notes of New York, New York Academy ofSciences XXXIII (2000), 35-36.
