Domination Coloring of Graphs

Yangyang Zhou, Dongyang Zhao, Mingyuan Ma and Jin Xu
Additional contact information
Yangyang Zhou: School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China
Dongyang Zhao: School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China
Mingyuan Ma: School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China
Jin Xu: School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China

Mathematics, 2022, vol. 10, issue 6, 1-12

Abstract: A domination coloring of a graph G is a proper vertex coloring of G , such that each vertex of G dominates at least one color class (possibly its own class), and each color class is dominated by at least one vertex. The minimum number of colors among all domination colorings is called the domination chromatic number, denoted by χ d d ( G ) . In this paper, we study the complexity of the k -domination coloring problem by proving its NP-completeness for arbitrary graphs. We give basic results and properties of χ d d ( G ) , including the bounds and characterization results, and further research χ d d ( G ) of some special classes of graphs, such as the split graphs, the generalized Petersen graphs, corona products, and edge corona products. Several results on graphs with χ d d ( G ) = χ ( G ) are presented. Moreover, an application of domination colorings in social networks is proposed.

Keywords: domination coloring; domination chromatic number; split graphs; generalized Petersen graphs; corona products; edge corona products (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/6/998/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/6/998/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:6:p:998-:d:775622

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().