Results on the maximal Roman domination number in graphs

Subject Areas : Statistics

Maryam Kamalipashakolaee ¹ (Department of Mathematics, Babol Noshirvani University of Technology, Babol, Iran)
Hossein Abdollahzadeh Ahangar ² (Department of Mathematics, Babol Noshirvani University of Technology, Babol, Iran)
Mehran Motiee ³ (Department of Mathematics, Babol Noshirvani University of Technology, Babol, Iran)
Seyed Mahmoud Sheikholeslami ⁴ (Department of Mathematics Azarbaijan Shahid Madani University Tabriz-Iran)

Received: 2019-04-07 Accepted : 2019-07-21 Published : 2020-08-22

Keywords: عدد احاطه‌گر رومی, تابع احاطه‌گر رومی ماکسیمال, تابع احاطه‌گر رومی, عدد احاطه‌گر رومی ماکسیمال,

Abstract :

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.

References:

[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 ‎m‎aximal Roman ‎domination‎ in ‎graphs, ‎‎Int. ‎‎J. ‎Comput‎. ‎Math‎. ‎‎93(7)‎‎ (201‎6‎‎) ‎‎1093-1102‎‎.‎‎

 

[3] ‎H. Abdollahzadeh ‎Ahangar, ‎‎M. ‎Chellali, D‎. ‎Kuziak, ‎and ‎V. ‎Samodivkin‎‎, ‎Connected ‎graphs with ‎m‎aximal 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 ‎i‎n ‎graphs‎‎,‎‎‎ Discrete ‎Math. ‎27‎8‎‎‎‎‎‎ (2004)‎‎11-22.‎‎‎

 

[5] ‎A. Hansberg, N. Jafari Rad, and ‎L. Volkmann,‎‎‎ Ve‎rtex 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),‎‎ Fundame‎‎ntals of ‎Domination in ‎Graphs‎,‎‎‎‎‎‎‎‎ Marce‎l Dekker, ‎‎‎‎‎‎Inc., ‎New ‎York, ‎1998.‎ ‎‎

 

[8] ‎V.R. ‎Kulli ‎and ‎B. ‎Janakiram,‎ The ‎maximal ‎domination ‎number ‎of a ‎graph‎‎, ‎‎‎Graph Theory Notes ‎of‎New ‎York, ‎New ‎York ‎Academy ‎of ‎Sciences ‎XXXIII ‎(1997‎)‎, ‎11-13.

‎

[9] V.R. ‎Kulli ‎a‎nd ‎B. ‎Janakiram‎‎‎, A note ‎on ‎maximal domination ‎number ‎of a ‎graph‎, ‎‎Graph ‎‎‎Theory Notes ‎of New ‎York‎, ‎‎‎‎‎New ‎York ‎Academy ‎of‎‎Sciences ‎XXXIII ‎(2000)‎, ‎35-36.