گراف همسایه مشترک

محورهای موضوعی : آمار

سمانه حسین‌زاده ¹ , علی ایرانمنش ² , اسما حمزه ³ , محمدعلی حسین‌زاده ⁴

1 - دانشکده علوم ریاضی، دانشگاه تربیت مدرس، تهران، ایران.
2 - دانشکده علوم ریاضی، دانشگاه تربیت مدرس، تهران، ایران.
3 - دانشکده علوم ریاضی، دانشگاه تربیت مدرس، تهران، ایران.
4 - دانشکده علوم ریاضی، دانشگاه تربیت مدرس، تهران، ایران.

تاریخ دریافت : 1394/11/01 تاریخ پذیرش : 1395/01/31 تاریخ انتشار : 1395/03/01

کلید واژه: Common neighborhood graph, Hamiltonian cycle, Clique number, Graph operation,

چکیده مقاله :

فرض کنید ‎G یک گراف ساده با مجموعه رأس‌های ‎است. گراف همسایه مشترک که با  ‎ نشان داده می‌شود، گرافی است با مجموعه رأس‌های‎  و دو رأس در آن مجاورند اگر دست کم یک همسایه مشترک داشته باشند. در این مقاله گراف همسایه مشترک تعدادی گراف‌های ترکیبی را محاسبه می‌کنیم. همچنین به بررسی رابطه همیلتونی بودن گراف و  پرداخته و کران پایینی برای عدد خوشه گراف ‎  برحسب عدد خوشه گراف  به دست می‌آوریم. در ادامه نشان می‌دهیم عدد رنگی کلی گراف ‎  به وسیله عدد رنگی‎  محدود می‌شود.

چکیده انگلیسی:

Let G be a simple graph with vertex set {v1, v2, … , vn}. The common neighborhood graph of G, denoted by con(G), is a graph with vertex set {v1, v2, … , vn}, in which two vertices are adjacent if and only if they have at least one common neighbor in the graph G. In this paper, we compute the common neighborhood of some composite graphs. In continue, we investigate the relation between hamiltonicity of graph G and con(G). Also, we obtain a lower bound for the clique number of con(G) in terms of clique number of graph G. Finally we state that the total chromatic number of G is bounded by chromatic number of con(T(G)).