کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650268 1342482 2009 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Vertex reconstruction in Cayley graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Vertex reconstruction in Cayley graphs
چکیده انگلیسی

In this survey paper we review recent results on the vertex reconstruction problem (which is not related to Ulam’s problem) in Cayley graphs. The problem of reconstructing an arbitrary vertex xx from its rr-neighbors, that are, vertices at distance at most rr from xx, consists of finding the minimum restrictions on the number of rr-neighbors when such a reconstruction is possible. We discuss general results for simple, regular and Cayley graphs. To solve this problem for given Cayley graphs, it is essential to investigate their structural and combinatorial properties. We present such properties for Cayley graphs on the symmetric group Symn and the hyperoctahedral group Bn (the group of signed permutations) and overview the main results for them. The choice of generating sets for these graphs is motivated by applications in coding theory, computer science, molecular biology and physics.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 3, 28 February 2009, Pages 548–559
نویسندگان
,