گرافهای دوری صحیح چندبخشی

در این مقاله، گراف­های دوری صحیح چند بخشی ICG (n, D) از مرتبه دلخواه n، که n عدد صحیح مثبتی است را مشخص می­شود. در اینجا ICG (n, D) گرافی است که رئوس آن اعضای گروه  است و یال­های آن مجموعه    می­باشد و D مجموعه­ای از مقسوم علیه­های مثبت عدد صحیح n است. این دسته از گراف­ها را به دلیل فرم مجموعه یال­های آن، گراف­های ب.م.م نامیده میشود. گراف دوبخشی G گرافی است که مجموعه رئوس آن را بتوان به دو زیرمجموعه X,Y طوری افراز کرد که هیچ دو راسی در X و هیچ دو راسی در Y مجاور نباشند. گراف دوبخشی را کامل گفته میشود هرگاه هر راس در X، به تمام رئوس Y متصل باشد. این گراف را با  نمایش داده میشود اگر  و . گراف­های چند بخشی، نیز مانند گراف دوبخشی تعریف می­شوند.

Keywords:

گراف کیلی , گراف صحیح , گراف دوری , گراف چندبخشی