کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872062 | 681717 | 2016 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The simultaneous metric dimension of graph families
ترجمه فارسی عنوان
ابعاد متراکم همزمان خانواده گراف
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let G=(V,E) be a connected graph. A vertex vâV is said to resolve two vertices x and y if dG(v,x)â dG(v,y). A set SâV is said to be a metric generator for G if any pair of vertices of G is resolved by some element of S. A minimum cardinality metric generator is called a metric basis, and its cardinality, dim(G), the metric dimension of G. A set SâV is said to be a simultaneous metric generator for a graph family G={G1,G2,â¦,Gk}, defined on a common (labeled) vertex set, if it is a metric generator for every graph of the family. A minimum cardinality simultaneous metric generator is called a simultaneous metric basis, and its cardinality the simultaneous metric dimension of G. We obtain sharp bounds for these invariants for general families of graphs and calculate closed formulae or tight bounds for the simultaneous metric dimension of several specific graph families. For a given graph G we describe a process for obtaining a lower bound on the maximum number of graphs in a family containing G that has simultaneous metric dimension equal to dim(G). It is shown that the problem of finding the simultaneous metric dimension of families of trees is NP-hard. Sharp upper bounds for the simultaneous metric dimension of trees are established. The problem of finding this invariant for families of trees that can be obtained from an initial tree by a sequence of successive edge-exchanges is considered. For such families of trees sharp upper and lower bounds for the simultaneous metric dimension are established.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 198, 10 January 2016, Pages 241-250
Journal: Discrete Applied Mathematics - Volume 198, 10 January 2016, Pages 241-250
نویسندگان
Yunior RamÃrez-Cruz, Ortrud R. Oellermann, Juan A. RodrÃguez-Velázquez,