کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648214 1342398 2012 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The distinguishing numbers of graphs on closed surfaces
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The distinguishing numbers of graphs on closed surfaces
چکیده انگلیسی

A graph GG is said to be dd-distinguishable   if there is a labeling c:V(G)→{1,2,…,d}c:V(G)→{1,2,…,d} such that no automorphism of GG other than the identity map preserves the labels of vertices given by cc. The smallest dd for which GG is dd-distinguishable is called the distinguishing number   of GG. We shall prove that every 4-representative triangulation on a closed surface, except the sphere, is 2-distinguishable after establishing a general theorem on the distinguishability of polyhedral graphs faithfully embedded on closed surfaces, and show that there is an upper bound for the distinguishing number of triangulations on a given closed surface, applying the re-embedding theory of triangulations.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 5, 6 March 2012, Pages 973–991
نویسندگان
,