بررسی بیشینه تعداد رده های احاطه گر در رنگ آمیزی یک گراف

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

مرتضی فغانی ¹ (دانشکده ریاضی، دانشگاه پیام نور، کدپستی 3697-19395 تهران، ایران)

تاریخ دریافت : 1396/07/03 تاریخ پذیرش : 1397/06/14 تاریخ انتشار : 1398/10/01

کلید واژه: Dominating Coloring Classes, Dominating Sets, Dominating Color Number, Chromatic number, Graph Coloring,

چکیده مقاله :

در این مقاله، عدد رنگی χ-احاطه گر، یعنی d_χ (G) در یک گراف G مورد بررسی قرار می گیرد. این عدد برابر است با ماکزیمم تعداد رده های رنگی که احاطه گر (یا تسلطی) بوده و G توسط χ(G) رنگ، رنگ آمیزی می شود. همچنین، نشان خواهیم داد که d_χ (G∨H)=d_χ (G)+d_χ (H) است بطوریکه G∨H به معنای الحاق G و H است. نتیجه فوق به ما کمک می کند که رده های گراف هایی که d_χ (G)>1 و d_χ (G)=χ(G) است را مشخص نماییم. همچنین در این مقاله، برخی نتایج در ارتباط با عدد رنگی χ-احاطه گر یک گراف ارائه می شود که مرتبط با سوالات مطرح شده در برخی مقالات اخیر حول مشخص سازی گراف های همبند G براساس مقدار d_χ (G) می باشد. در بخش پایانی مقاله، براساس قضایای حاصل این پرسش را مطرح می کنیم که آیا گراف های بدون مثلث G با شرط d_χ (G )=χ(G)=k موجود است؟آیا G دارای یک زیرگراف k-رنگ پذیر یکتا است یا خیر؟ بعلاوه، آیا یافتن چنین گراف هایی از کمر به اندازه کافی بزرگ میسر می باشد؟

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

In this paper we investigate the dominating- -color number، of a graph G. That is the maximum number of color classes that are also dominating when G is colored using colors. We show that where is the join of G and H. This result allows us to construct classes of graphs such that and thus provide some information regarding two questions raised in [1] and [2].

منابع و مأخذ:

[1] Arumugam, S., Haynes, T.W., Henning, M.A. and Nigussie, Y., Maximal Independent Sets in Minimum Colorings. Discrete Mathematics, 311 (2011) 1158-1163.

 

[2] Arumugam, A., Hamid, I.S. and Muthukamatchi, A., Independent Domination and Graph Clorings. Ramanujan Mathematical Society Lecture Notes Series, 7 (2008) 195-203. 

 

[3] Arumugam, S. and Chandrasekar, K.R., Minimal Dominating Sets in Maximum Domatic Partitions. Australasian Journal of Combinatorics, 52 (2012) 281-292. 

 

[4] Li, S., Zhang, H. and Zhang, X., Maximal Independent Sets in Bipartite Graphs with at Least One Cycle. Discrete Mathematics and Theoretical Computer Science, 15 (2013) 243-258.