Color Class Dominating Sets on Regular Graphs of Degree 5

Abstract

Let G=(V,E)be a graph. A color class dominating set of G is a proper coloring C of G with extra property that every color class in C is dominated by a vertex in G. A color class dominating set is said to be minimal color class dominating set if no proper subset of C is a color class dominating set of G. The color class domination number of G is the minimum cardinality taken over all minimal color class dominating sets of G and is denoted by ?_? (G). Here we also obtain ?_? (G) of regular graph degree 5.

Introduction

The paper studies color class domination in finite, undirected graphs, focusing on regular graphs of degree 5. It reviews key graph theory concepts such as neighborhoods, dominating sets, chromatic number, and introduces the color class domination number γχ(G)\gamma_\chi(G)γχ?(G), defined as the minimum size of a proper coloring in which each color class is dominated by a vertex. This concept, originally introduced by Vijayalekshmi et al., is applied to analyze structural properties of regular graphs.

The main result establishes that for a 5-regular graph GGG of even order nnn, the color class domination number satisfies

γχ(G)=n2orn2−2.\gamma_\chi(G) = \frac{n}{2} \quad \text{or} \quad \frac{n}{2} - 2.γχ?(G)=2n?or2n?−2.

Two cases are examined: graphs containing triangles and graphs without triangles. For graphs with triangles, a specific vertex coloring shows that γχ(G)=n2\gamma_\chi(G) = \frac{n}{2}γχ?(G)=2n?. For triangle-free graphs, an alternative coloring construction yields γχ(G)=n2−2\gamma_\chi(G) = \frac{n}{2} - 2γχ?(G)=2n?−2. Illustrative examples support both cases, confirming the theorem.

Conclusion

All graphs considered in this paper are finite, undirected graphs and we follow standard definitions of graph theory [2]. Let G=(V,E)be a graph of order p. The open neighborhood N(v)of vertexv?V(G)consist of the set of all vertices adjacent to v. The closed neighborhood of v is N[v]=N(v)?{v}. For a set S?V, the open neighborhood N(S)is defined to be U_v?S N(v), and the closed neighborhood of S isN[S]=N(S)?S for any subset H of vertices of G, the induced sub graph is the maximal sub graph of G with vertex set H.

References

[1] A. Vijayalekshmi, Total dominator colorings in graphs, International Journal of Advancements in Research Technology, Vol. 1, No. 4, pp. 1-6, 2012. [2] A. Vijayalekshmi and A.E. Prabha, Introduction of color class dominating set in Graphs, Malaya Journal of Mathematik, Vol. 8, No. 4, pp. 2186-2189, 2020. [3] A. Vijayalekshmi and S.G. Vidhya, Color class dominating sets in path and cycle related graphs Malaya Journal of Matematik, Vol. 09, No. 01, 1237-1240, 2021 [4] A. Vijayalekshmi and P. Niju, An Introduction of Dominator color class dominating sets in Graphs, Malaya Journal of Matematik, Vol.9, No.1, pp. 1015-1018, 2021. [5] A. Vijayalekshmi and J. VirjinAlangara Sheeba, Total Dominator Chromatic Number of Paths Cycles and Ladder graphs, International Journal of Contemporary Mathematical Sciences, Vol. 13, No. 5, pp. 199–204, 2018. [6] A. Vijayalekshmi and S. Anusha, Dominator Chromatic Number on Various Classes of Graphs, International Journal of Scientific Research and Reviews, Vol. 9, No. 3, pp. 91–01, 2020. [7] A. Vijayalekshmi and S.G. Vidhya, Dominator color class dominating sets in triangular ladder and mobius ladder graphs, Malaya Journal of Matematik, Vol. 09, No. 01, 1241-1243, 2021 [8] F. Harrary, Graph Theory, Addition – Wesley Reading Mass, 1969. [9] A. Vijayalekshmi and S.G. Vidhya, Dominator color class dominating sets in Grid graphs Journal of Computational Analysis and Applications, Vol. 33, No. 08, 385-389, 2024 [10] Terasa W. Haynes, Stephen T. Hedetniemi, Peter J Slater, Determination in Graphs, Maral Dekker, New York, 1998. [11] A. Vijayalekshmi and A.E.Prabha, Color class dominations sets in various classes of Graphs, Malaya Journal of Matematik, Vol. 9, No. 1, pp. 195-198, 2021 [12] A.E. Prabha and A. Vijayalekshmi, ‘Color class dominating sets in ladder and grid Graphs, Malaya Journal of Matematik, Vol. 9, No. 1, 993-995, 2021 [13] A.E. Prabha and A. Vijayalekshmi, Color Class Dominating Sets on Cartesian Product of Path and Cycle Related Graphs, Adalya Journal, Vol. 9, No. 7, pp. 16-25, 2022 [14] P. Niju and A. Vijayalekshmi, Color Class Dominating sets in Open Ladder and Slanting Ladder Graphs, International Journal of New Innovations in Engineering and Technology, Vol. 17, No. 1, pp. 57-61, 2021. [15] A. Vijayalekshmi and P. Niju, Color Class Dominating sets in Umbrella Graph and Dutch Windmill Graphs, Infokara research, Vol. 10, No. 12, pp. 38-48, 2021

Copyright

Copyright © 2026 Dr. A. Vijayalekshmi, S. G. Vidhya. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.