ALGORITHMIC ASPECTS OF ROMAN GRAPHS
محل انتشار: مجله ساختارهای جبری، دوره: 9، شماره: 1
سال انتشار: 1400
نوع سند: مقاله ژورنالی
زبان: انگلیسی
مشاهده: 182
فایل این مقاله در 18 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_JAS-9-1_010
تاریخ نمایه سازی: 13 اردیبهشت 1400
چکیده مقاله:
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.
کلیدواژه ها:
نویسندگان
A. Poureidi
Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran.
مراجع و منابع این مقاله:
لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :