A Characterization of Trees with Large Roman Domination Number

Document Type: research paper

Authors

1 Department of Basic Science Babol Noshirvani University of Technology, Babol, Iran

2 Department of Mathematics Shahrood University of Technology, Shahrood, Iran

Abstract

 
A Roman dominating function (RDF) on a graph G = 􀵫V،E􀵯 is a function f: V(G) → {0،1،2}
satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one
vertex v for which f(v) = 2. The weight of an RDF f is w(f) = Σ􀭴∈􀭚 f(v). The Roman
domination number of G is the minimum weight of an RDF in G. In this paper, we
characterize all trees T of order n whose Roman domination number is n − 3.

Keywords


Article Title [Persian]

دسته بندی درخت‌ها با عدد رومی بزرگ

Authors [Persian]

  • حسین عبداله زاده آهنگر 1
  • مهلا خیبری 1
  • نادر جعفری راد 2
1 گروه ریاضی، دانشگاه صنعتی نوشیروانی بابل، بابل، ایران
2 گروه ریاضی، دانشگاه صنعتی شاهرود، شاهرود، ایران
Abstract [Persian]

تابع  {2,1,0}=(G)f:v یک تابع احاطه‌گر رومی (RDF) برای گراف G نامیده می­شود هرگاه برای هر راس 􀝑 با شرط f(u) = 0 راسی مجاور با آن مانند v وجود داشته باشد به­ طوری که 2=f(u). وزن یک RDF f برابر است با 􀝓(􀝂) = Σ􀯩∈􀯏 􀝂(􀝒). عدد احاطه‌گر رومی گراف G را که با نماد 􀟛􀯋 نمایش می­دهیم کمترین وزن یک RDF در گراف  است. در این مقاله کلیه درخت­های از مرتبه  با عدد احاطه‌گر رومی ، را دسته بندی می‌کنیم. 

Keywords [Persian]

  • تابع احاطه گر رومی
  • عدد احاطه گر رومی