On Domatic and Total Domatic Numbers of Product Graphs

MaRDI QIDQ6363245zbMATH OpenFDO

Authors P. Francis, Deepak Rajendraprasad

Publication date 19 March 2021

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: A emph{domatic} (emph{total domatic}) emph{$k$-coloring} of a graph $G$ is an assignment of $k$ colors to the vertices of $G$ such that each vertex contains vertices of all $k$ colors in its closed neighborhood (neighborhood). The emph{domatic} (emph{total domatic}) emph{number} of $G$, denoted $d(G)$ ($d_t(G)$), is the maximum $k$ for which $G$ has a domatic (total domatic) $k$-coloring. In this paper, we show that for two non-trivial graphs $G$ and $H$, the domatic and total domatic numbers of their Cartesian product $GcartH$ is bounded above by $max|V(G)|,|V(H)|$ and below by $maxd(G),d(H)$. Both these bounds are tight for an infinite family of graphs. Further, we show that if $H$ is bipartite, then $d_t(GcartH)$ is bounded below by $2min{d}_t(G),d_t(H)$ and $d(GcartH)$ is bounded below by $2mind(G),d_t(H)$. These bounds give easy proofs for many of the known bounds on the domatic and total domatic numbers of hypercubes cite{chen,zel4} and the domination and total domination numbers of hypercubes cite{har,joh} and also give new bounds for Hamming graphs. We also obtain the domatic (total domatic) number and domination (total domination) number of $n$-dimensional torus $mathopcartlimit{s}_{i=1}^n{C}_{k_i}$ with some suitable conditions to each $k_i$, which turns out to be a generalization of a result due to Gravier cite{grav2} %[emph{Total domination number of grid graphs}, Discrete Appl. Math. 121 (2002) 119-128] and give easy proof of a result due to Klavv{z}ar and Seifter cite{sand}.

This page was built for publication: On Domatic and Total Domatic Numbers of Product Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6363245)