On the Maximum Number of Dominating Classes in Graph Coloring

Document Type: research paper

Author

Department of Mathematics, Payame Noor University, P.O.Box 19395-3697, Tehran, Iran

Abstract

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].
 

Keywords


Article Title [Persian]

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

Author [Persian]

  • مرتضی فغانی
دانشکده ریاضی، دانشگاه پیام نور، کدپستی 3697-19395 تهران، ایران
Abstract [Persian]

در این مقاله، عدد رنگی χ-احاطه گر، یعنی 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-رنگ پذیر یکتا است یا خیر؟ بعلاوه، آیا یافتن چنین گراف هایی از کمر به اندازه کافی بزرگ میسر می باشد؟

Keywords [Persian]

  • رنگ آمیزی گراف
  • مجموعه های احاطه گر
  • رده های رنگ آمیزی احاطه گر
  • عدد رنگی
  • عدد رنگی احاطه گر
[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.