ALGORITHMIC ASPECTS OF ROMAN GRAPHS
- سال انتشار: 1400
- محل انتشار: مجله ساختارهای جبری، دوره: 9، شماره: 1
- کد COI اختصاصی: JR_JAS-9-1_010
- زبان مقاله: انگلیسی
- تعداد مشاهده: 189
نویسندگان
Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran.
چکیده
Let $G=(V, E)$ be a graph. A set $S \subseteq V$ is called a dominating set of $G$ if for every $v\in V-S$ there is at least one vertex $u \in N(v)$ such that $u\in S$. The domination number of $G$, denoted by $\gamma(G)$, is equal to the minimum cardinality of a dominating set in $G$. A Roman dominating function (RDF) on $G$ is a function $f:V\longrightarrow\{۰,۱,۲\}$ such that every vertex $v\in V$ with $f(v)=۰$ is adjacent to at least one vertex $u$ with $f(u)=۲$. The weight of $f$ is the sum $f(V)=\sum_{v\in V}f (v)$. The minimum weight of a RDF on $G$ is the Roman domination number of $G$, denoted by $\gamma_R(G)$. A graph $G$ is a Roman Graph if $\gamma_R(G)=۲\gamma(G)$. In this paper, we first study the complexity issue of the problem posed in [E.J. Cockayane, P.M. Dreyer Jr., S.M. Hedetniemi and S.T. Hedetniemi, On Roman domination in graphs, \textit{Discrete Math.} ۲۷۸ (۲۰۰۴), ۱۱--۲۲], and show that the problem of deciding whether a given graph is a Roman graph is NP-hard even when restricted to chordal graphs. Then, we give linear algorithms that compute the domination number and the Roman domination number of a given unicyclic graph. Finally, using these algorithms we give a linear algorithm that decides whether a given unicyclic graph is a Roman graph.کلیدواژه ها
Dominating set, Roman dominating function, Algorithm, ۳-SAT Problem, unicyclic graphاطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.