Dominated Coloring of Certain Graphs

Document Type : Research Paper

Authors

1 Department of Mathematics, Ferdowsi University of Mashhad, Mashhad, Iran

2 Department of Mathematics, Quchan University of Technology, Quchan, Iran

3 Department of Mathematics, University of Mazandaran, Babolsar, Iran

Abstract

A proper coloring of a graph G is called a dominated coloring whenever each color class is dominated by at least one vertex. The minimum number of colors among all dominated colorings of G is called its dominated chromatic number, denoted by χdom(G). We define a parameter related to dominated coloring, namely dominated chromatic covering. For a minimum dominated coloring of G, a set of vertices S is called a dominated chromatic covering if each color class is dominated by a vertex of S. The minimum cardinality of a dominated chromatic covering of G is called its dominated chromatic covering number, denoted by θχdom(G) . It is clear that θχdom(G) ≤ χdom(G). In this paper, we obtain the dominated chromatic number and θχdom(G) when G is middle and total graph of paths and cycles.

Keywords

References

  1. M. Chellali, F. Maffray, Dominator colorings in some classes of graphs, Graphs Combin., 28, 97–107 (2012).
  2. F. Choopani, A. Jafarzadeh, A. Erfanian, D. A. Mojdeh, On dominated coloring of graphs and some Nardhaus–Gaddum–type relations, Turk. J. Math., 42, 2148–2156 (2018).
  3. F. Harary, Graph Theory, Addison-Wesley Publishing Company, Boston (1969).
  4. T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of Domination in Graphs, CRC Press, New York (1998).
  5. A. P. Kazemi, Total dominator chromatic number of a graphs, Trans. Combin., 4(2), 57–68 (2015).
  6. H. B. Merouane, M. Haddad, M. Chellali, H. Kheddouci, Dominated colorings of graphs, Graphs Combin., 31, 713–727 (2015).
  7. D. A. Mojdeh, Defining sets in (proper) vertex colorings of the Cartesian product of a cycle with a complete graph , Discuss. Math. Graph Theory, 26(1), 59–72 (2006).
  8. D. A. Mojdeh, On conjectures on the defining set of (vertex) graph colourings, Australas. J. Combin., 34, 153–160 (2006).
  9. D. A. Mojdeh, M. Alishahi, Outer independent global dominating set of trees and uni[1]cyclic graphs, Electron. J. Graph Theory Appl. 7(1), 121–145 (2019).
  10. D. A. Mojdeh, M. Alishahi, M. Chellali, Trees with the same global domination number as their square, Australas. J. Combin., 66, 288–309 (2016).
  11. D. B. West, Introduction to Graph Theory (Vol. 2), Second Edition, Upper Saddle River, Prentice hall (2001).
Global Analysis and Discrete Mathematics
Volume 7, Issue 1
November 2022
Pages 89-99

Files

History

  • Receive Date: 14 October 2022
  • Revise Date: 20 October 2022
  • Accept Date: 21 October 2022

Share

How to cite

Statistics