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

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

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

تاریخ دریافت : 1397/08/07 تاریخ پذیرش : 1398/08/18 تاریخ انتشار : 1399/04/11

کلید واژه: dominating set, Chromatic number, Incidence coloring,

چکیده مقاله :

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

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

In this paper, the concept of incidence domination number of graphs is introduced and the incidence dominating set and the incidence domination number of some particular graphs such as paths, cycles, wheels, complete graphs and stars are studied.

منابع و مأخذ:

 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