تعداد نشریات | 5 |
تعداد شمارهها | 108 |
تعداد مقالات | 1,228 |
تعداد مشاهده مقاله | 1,147,080 |
تعداد دریافت فایل اصل مقاله | 1,006,010 |
Irredundance chromatic number and gamma chromatic number of trees | ||
Communications in Combinatorics and Optimization | ||
مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 22 مرداد 1403 اصل مقاله (353.8 K) | ||
نوع مقاله: Short notes | ||
شناسه دیجیتال (DOI): 10.22049/cco.2024.29328.1945 | ||
نویسندگان | ||
David A Kalarkop1؛ Pawaton Kaemawichanurat* 1، 2 | ||
1Department of Mathematics, Faculty of Science, King Mongkut’s University of Technology Thonburi, Thailand | ||
2Mathematics and Statistics with Application (MaSA) | ||
چکیده | ||
A vertex subset $S$ of a graph $G = (V, E)$ is irredundant if every vertex in $S$ has a private neighbor with respect to $S$. An irredundant set $S$ of $G$ is maximal if, for any $v \in V - S$, the set $S \cup \{v\}$ is no longer irredundant. The lower irredundance number of $G$ is the minimum cardinality of a maximal irredundant set of $G$ and is denoted by $ir(G)$. A coloring $\mathcal{C}$ of $G$ is said to be the irredundance coloring if there exists a maximal irredundant set $R$ of $G$ such that all the vertices of $R$ receive different colors. The minimum number of colors required for an irredundance coloring of $G$ is called the irredundance chromatic number of $G$, and is denoted by $\chi_{i}(G)$. A coloring $\mathcal{C}$ of $G$ is said to be the gamma coloring if there exists a dominating set $D$ of $G$ such that all the vertices of $D$ receive different colors. The minimum number of colors required for a gamma coloring of $G$ is called the gamma chromatic number of $G$, and is denoted by $\chi_{\gamma}(G)$. In this paper, we prove that every tree $T$ satisfies $\chi_{i}(T) = ir(T)$ unless $T$ is a star. Further, we prove that $\gamma(T) \leq \chi_{\gamma}(T) \leq \gamma(T) + 1$. We characterize all trees satisfying the upper bound. | ||
کلیدواژهها | ||
Irredundance chromatic number؛ gamma chromatic number؛ irredundance coloring؛ gamma coloring | ||
مراجع | ||
[1] L.W. Beineke and R.J. Wilson, Topics in Chromatic Graph Theory, Cambridge University Press, 2015.
[2] G. Chartrand and L. Lesniak, Graphs and Digraphs, sixth edition, Chapman & Hall London, 2016.
[3] R. Gnanaprakasam and I.S. Hamid, Gamma coloring of mycielskian graphs, Indian J. Sci. Technol. 15 (2022), no. 20, 976–982. https://doi.org/10.17485/IJST/v15i20.2324 [4] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, CRC press, 2013.
[5] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Domination in Graphs: Volume 2: Advanced Topics (1st ed.), Chapman & Hall/CRC Pure and Applied Mathematics, 1998.
[6] D.A. Kalarkop and P. Kaemawichanurat, On irredundance coloring and irredundance compelling coloring of graphs, arXiv preprint arXiv:2311.06161 (2023). | ||
آمار تعداد مشاهده مقاله: 54 تعداد دریافت فایل اصل مقاله: 169 |