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

نوع مقاله: مقاله پژوهشی

نویسنده

دانشگاه بوعلی سینا دانشکده علوم گروه ریاضی

چکیده

در این مقاله، گراف‌های دوری صحیح چندبخشی ICG (n, D) از مرتبه دلخواه n، که n عدد صحیح مثبتی است را مشخص می‌کنیم. در این‌جا ICG (n, D) گرافی است که رئوس آن اعضای گروه Z_n است و یال‌های آن مجموعه {{a ,b}:a ,b ∈ Z_n ,gcd⁡〖(a-b ,n)∈D〗 } می‌باشد و D مجموعه‌ای از مقسوم علیه‌های مثبت عدد صحیح n است. این دسته از گراف‌ها را به دلیل فرم مجموعه یال‌های آن، گراف‌های ب.م.م می‌نامیم. گراف دوبخشی G گرافی است که مجموعه رئوس آن را بتوان به دو زیر مجموعه X,Y طوری افراز کرد که هیچ دو رأسی در X و هیچ دو رأسی در Y مجاور نباشند. گراف دوبخشی را کامل گوییم هرگاه هر رأس در X، به تمام رئوس Y متصل باشد. این گراف را با K_(m,n) نمایش می‌دهیم، اگر |X|=m و |Y|=n. گراف‌های چندبخشی، نیز مانند گراف دوبخشی تعریف می‌شوند.

کلیدواژه‌ها



مقالات آماده انتشار، پذیرفته شده
انتشار آنلاین از تاریخ 14 تیر 1399
  • تاریخ دریافت: 27 خرداد 1399
  • تاریخ بازنگری: 21 مرداد 1399
  • تاریخ پذیرش: 14 تیر 1399