کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647345 1632416 2014 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Long geodesics in subgraphs of the cube
ترجمه فارسی عنوان
جیودیزهای بلند در زیرگرافهای مکعب
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

We show that any subgraph of the hypercube QnQn of average degree dd contains a geodesic of length dd, where by geodesic we mean a shortest path in QnQn. This result, which is best possible, strengthens a theorem of Feder and Subi. It is also related to the ‘antipodal colourings’ conjecture of Norine.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 326, 6 July 2014, Pages 29–33
نویسندگان
, ,