کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5776881 | 1413644 | 2017 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Toll number of the Cartesian and the lexicographic product of graphs
ترجمه فارسی عنوان
شماره تلفنی دکتیوسی و محصول واژگانی گراف
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
محاسبه توده، شماره تلفن، محصول گراف،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Toll convexity is a variation of the so-called interval convexity. A tolled walk T between two non-adjacent vertices u and v in a graph G is a walk, in which u is adjacent only to the second vertex of T and v is adjacent only to the second-to-last vertex of T. A toll interval between u,vâV(G) is a set TG(u,v)={xâV(G):x lies on a tolled walk between u and v}. A set SâV(G) is toll convex, if TG(u,v)âS for all u,vâS. A toll closure of a set SâV(G) is the union of toll intervals between all pairs of vertices from S. The size of a smallest set S whose toll closure is the whole vertex set is called a toll number of a graph G, tn(G). The first part of the paper reinvestigates the characterization of convex sets in the Cartesian product of two graphs. It is proved that the toll number of the Cartesian product of two graphs equals 2. In the second part, the toll number of the lexicographic product of two graphs is studied. It is shown that if H is not isomorphic to a complete graph, tn(GâH)â¤3â
tn(G). We give some necessary and sufficient conditions for tn(GâH)=3â
tn(G). Moreover, if G has at least two extreme vertices, a complete characterization is given. Furthermore, graphs with tn(GâH)=2 are characterized. Finally, the formula for tn(GâH) is given - it is described in terms of the so-called toll-dominating triples or, if H is complete, toll-dominating pairs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 10, October 2017, Pages 2488-2498
Journal: Discrete Mathematics - Volume 340, Issue 10, October 2017, Pages 2488-2498
نویسندگان
Tanja Gologranc, Polona Repolusk,