کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8902764 | 1632244 | 2017 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The forcing total restrained geodetic number and the total restrained geodetic number of a graph: Realizability and complexity
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Given two vertices u and v of a nontrivial connected graph G, the set I[u,v] consists all vertices lying on some uâv geodesic in G, including u and v. For SâV(G), the set I[S] is the union of all sets I[u,v] for u,vâS. A set SâV(G) is a total restrained geodetic set of G if I[S]=V(G) and the subgraphs induced by S and V(G)âS have no isolated vertex. The minimum cardinality of a total restrained geodetic set of G is the total restrained geodetic number gtr(G) of G and a total restrained geodetic set of G whose cardinality equals gtr(G) is a minimum total restrained geodetic set of G. A subset T of a minimum total restrained geodetic set S is a forcing subset for S if S is the unique minimum total restrained geodetic set of G containing T. The forcing total restrained geodetic number ftr(S) of S is the minimum cardinality of a forcing subset of S and the forcing total restrained geodetic number ftr(G) of G is the minimum forcing total restrained geodetic number among all minimum total restrained geodetic sets of G. In this article we determine all pairs a,b of integers such that ftr(G)=a and gtr(G)=b for some nontrivial connected graph G. Moreover, we show that the decision problem regarding that the total restrained geodetic number of a graph will be less than some positive integer r is NP-complete even when restricted to chordal graph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: AKCE International Journal of Graphs and Combinatorics - Volume 14, Issue 3, December 2017, Pages 242-250
Journal: AKCE International Journal of Graphs and Combinatorics - Volume 14, Issue 3, December 2017, Pages 242-250
نویسندگان
H. Abdollahzadeh Ahangar, M. Najimi, V. Samodivkin, Ismael G. Yero,