عدد احاطه‌ای هم-رومی در درخت ها
محورهای موضوعی : آمار
رعنا خوئیلر
1
(گروه ریاضی
دانشگاه شهید مدنی آذربایجان
تبریز-آیران)
مرضیه سرودی
2
(گروه ریاضی
دانشگاه شهید مدنی آذربایجان
تبریز-ایران)
کلید واژه: Roman dominating function, Roman domination number, co-Roman dominating function, grid, co-Roman domination number,
چکیده مقاله :
فرض کنید G=(V,E) یک گراف و f:V(G)→{0,1,2} یک تابع باشد. رأسv نسبت به تابعf محافظت‌شده است هرگاه f(v)>0 یا f(v)=0و v با رأسی به وزن مثبت مجاور باشد. تابع f، یک تابع احاطه‌گر هم-رومی (به اختصار CRDF) است هرگاه: (1) هر رأس درV محافظت‌شده باشد، و (2) هر رأسu∈V با وزن مثبت همسایه‌ای همچون v∈Vبا f(v)=0 داشته‌باشد به طوری‌که تابعf_uv:V→{0,1,2} تعریف‌شده به‌صورت f_uv (u)=f(u)-1 ، f_uv (v)=1 و برایx∈V-\{v,u} به‌صورت f_uv (x)=f(x)، هیچ رأس محافظت‌نشده‌ای نداشته‌باشد. وزنf به‌صورت ω(f)=∑_(v∈V)▒〖f(v)〗 تعریف می‌شود. عدد احاطه‌ای هم-رومی گراف G که با نماد γ_cr G) نمایش داده می‌شود، کمترین وزن در بین تمامی توابع احاطه‌گر هم-رومی گراف G می‌باشد. در این مقاله، ابتدا یک کران بالا برای عدد احاطه‌ای هم-رومی درخت‌ها برحسب تعداد رئوس، تعداد برگ‌ها و تعداد رئوس تکیه‌گاه درخت T ارائه می‌کنیم. همچنین ما کران‌هایی برای عدد احاطه‌ای هم-رومی یک درخت برحسب مرتبه و سایر پارامترهای احاطه‌ای آن به‌دست می‌آوریم.
Abstract: Let G=(V,E) be a graph and let f:V(G)→{0,1,2} be a function. A vertex v is protected with respect to f, if f(v)>0 or f(v)=0 and v is adjacent to a vertex of positive weight. The function f is a co-Roman dominating function, abbreviated CRDF if: (i) every vertex in V is protected, and (ii) each u∈V with positive weight has a neighbor v∈V with f(v)=0 such that the function f_uv:V→{0,1,2}, defined by f_uv (v)=1, f_uv (u)=f(u)-1 and f_uv (x)=f(x)for x∈V-\{v,u}, has no unprotected vertex. The weight of f is ω(f)=∑_(v∈V)▒〖f(v)〗. The co-Roman domination number of a graph G , denoted by γ_cr G), is the minimum weight of a co-Roman dominating function on G . In this paper, we first present an upper bound on the co-Roman domination number of trees in terms of order, the number of leaves and supports. Then we find bounds on the co-Roman domination number of a graph and its other dominating parameters .
[1] H. Abdollahzadeh Ahangar, M. Chellali and S.M. Sheikholeslami, "On the double Roman domination ingraphs", Discrete. Appl. Math. 232 (2017) 1-7.
[2] S. Arumugam, K. Ebadi, M. anrique, "Co-Roman dominaton in graphs", Indian Acad. Sci.(Math. Sci) (2014).
[3] R.A. Beeler, T.W. Haynes and S.T. Hedetniemi, "Double Roman domination", Discrete Appl. Math. 211 (2016) 23-29.
[4] B. Bre ar, T. K. umenjak, "Onthe 2-rainbow domination in graphs", Discrete Appl. Math. 155 (2007)2394-2400.
[5] E. W. Chambers, B. Kinnersley, N. Prince and D. B. West, "Extremal problems for Roman domination", SIAM J. Discreter. Math 23 (2009)1575-1586.
[6] M. Chellali and T. W. Haynes andS. T. Hedetniemi, "Bounds on weak Roman and 2-rainbow domination numbers", Discrete. Appl. Math. 178 (2014) 27-32.
[7] M. Chellali, T.W. Haynes, S.T. Hedetniemi and A. MacRae, "Roman {2}-domination", Discrete Appl. Math. 204 (2016) 22-28.
[8] E. J. Cockayne, P. A. Dreyer Jr., S. M. Hedetniemi and S. T. Hedetniemi,
"Roman domination in graphs", Discrete Math. 278 (2004) 11-22.
[9] N. Dehgardi, S.M. Sheikholeslami, M. Soroudi and L. Volkmann,"Bounds on the co-Roman domination number in graphs", Asian-Eur. J. Math. (to appear).
[10] S. Fujita and M. Furuya, "Difference between 2-rainbow domination and Roman domination in graphs", Discete. Appl. Math 161 (2013) 806-812.
[11]T. W. Haynes, S. T. Hedetniemi and P. J. Slater, "Fundamentals of Domination in Graphs", Marcel Dekker, Inc, New York, (1998).
[12] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, "Dominatin in Graphs: Advanced Topics", Marcel Dekker, Inc, New York, (1988).
[13] M. A. Henning, "Defending the Roman Empire-A new strategy", Discrete Math. 266(2003) 239-251.
[14] P. Roushini Leely Pushpam, "Weak Roman domination in graphs", Discuss. Math. Graph Theory 31 (2011)115-128.
[15] Z. Shao, S.M. Sheikholeslami, M. Soroudi, L. Volkmann and X. Liu, "On the co-Roman domination in graphs", Discuss. Math. Graph Theory (to appear).
[16] D. B. West, "Introduction to Graph Theory (second edition) ", Prentice Hall, USA, (2001).
[17] Y. Wu and N. Jafari Rad, "Bounds on the 2-rainbow domination number of graphs", Graphs Combin. 29 (2013)1125-1133.
