عدد احاطه گری وقوعی گراف ها

الموضوعات :

پریسا عزیزی کشاورز ¹ (گروه ریاضی، دانشگاه آزاد اسلامی واحد علوم و تحقیقات، تهران، ایران)
ابوالفضل تهرانیان ² (گروه ریاضی، دانشگاه آزاد اسلامی واحد علوم و تحقیقات، تهران، ایران)

تاريخ الإرسال : 20 الإثنين , صفر, 1440 تاريخ التأكيد : 12 السبت , ربيع الأول, 1441 تاريخ الإصدار : 10 الأربعاء , ذو القعدة, 1441

الکلمات المفتاحية: dominating set, Chromatic number, Incidence coloring,

ملخص المقالة :

در این مقاله مفهوم عدد احاطه گری وقوعی گراف ها معرفی شده و مجموعه احاطه گر وقوعی و عدد احاطه گری وقوعی برخی از گراف های خاص مانند گراف مسیر، گراف دور، گراف چرخ، گراف کامل و گراف ستاره مورد مطالعه قرار گرفته است. ابتدا عدد احاطه گری وقوعی تعدادی از گراف های خاص مانند گراف مسیر، گراف دور، گراف ستاره، گراف چرخ و همچنین گراف کامل محاسبه شده است. سپس عدد رنگی احاطه گر وقوعی برخی از گراف های ذکر شده محاسبه شده و نتایجی در این زمینه به دست آمده است. عدد رنگی احاطه گر وقوعی هر گراف در واقع عدد رنگی احاطه گر برای گراف وقوع است. نشان داده شده که مقدار این عدد برای گراف مسیر از مرتبه n برابراست با ⌈(2(n-1))⁄5⌉+3. همچنین برای گراف دور از مرتبه n مقدار آن برابراست با ⌈2n⁄5⌉+3 . ثابت شده که عدد رنگی احاطه گر وقوعی برای گراف ستاره S_n برابر n+1 بوده و همچنین برای گراف کامل از مرتبه n نشان داده شده که این مقدار برابر n است.

المصادر:

 R.A. Brualdi, J.J.Q. Massey. Incidenceand strong edge colorings of graphs. Discrete Math 122: 51-58 (1993)

 

 G. Chartrand, P. Zhang. Introduction to graph theory. McGraw Hill, Boston (2005)

 

 R. M. Gera, S. Horton, C. Rasmussen. Dominator Coloring and Safe Clique Partitions. Congressus Numerantium 181 (7-9): 19-32 (2006)

 

 R. M. Gera. On Dominator colorings in graphs. Graph Theory Notes of New York, LIT 25-30 (2007)

 

 B. Guiduli. On incidence coloring and star arboricity of graphs. Discrete Math 163: 275-278 (1997)

 

 R.M. Gera. On the dominator colorings in bipartite graphs. ITNG.IEEE 1-6 (2007)

 

 O.Ore. Theory of graphs. no.38 in American Mathematical Society Publications, AMS, Providence (1962)

 

 T.Haynes, M. Henning. Domination in graphs of maximum degree 3. Discrete Math 292:131-141 (2005)

 

 F.V. Fomin, D.M. Thilikos. Dominating sets in planar graphs. Branch-width and exponential speed-up, Siam Journal on Computing 36(2): 281-309 (2006)

 

 M.Chellali, F. Maffray. Dominator colorings in some classes of graphs. Graphs and Combin 1-11(2011)

 

 I. Algor and N. Alon. The star arboricity of graphs. Discrete Math