کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4653258 1632762 2016 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
There are no finite partial cubes of girth more than 6 and minimum degree at least 3
ترجمه فارسی عنوان
مکعب های جزئی از محدب بیش از 6 و حداقل درجه حداقل 3 است
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

Partial cubes are graphs isometrically embeddable into hypercubes. We analyze how isometric cycles in partial cubes behave and derive that every partial cube of girth more than 6 must have vertices of degree less than 3. As a direct corollary we get that every regular partial cube of girth more than 6 is an even cycle. Along the way we prove that every partial cube GG with girth more than 6 is a tree-zone graph and therefore 2n(G)−m(G)−i(G)+ce(G)=22n(G)−m(G)−i(G)+ce(G)=2 holds, where i(G)i(G) is the isometric dimension of GG and ce(G)ce(G) its convex excess.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 55, July 2016, Pages 62–72
نویسندگان
,