On Domatic and Total Domatic Numbers of Cartesian Products of Graphs

A domatic (resp. total domatic) 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 (resp. open neighborhood). The domatic (resp. total domatic) number of G, denoted d(G) (resp. dt(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d_t (G)$$\end{document}), is the maximum k for which G has a domatic (resp. 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 G□H\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G \mathbin \square H$$\end{document} is bounded above by max{|V(G)|,|V(H)|}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\max \{|V(G)|, |V(H)|\}$$\end{document} and below by max{d(G),d(H)}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\max \{d(G), d(H)\}$$\end{document}. Both these bounds are tight for an infinite family of graphs. Further, we show that if H is bipartite, then dt(G□H)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d_t(G \mathbin \square H)$$\end{document} is bounded below by 2min{dt(G),dt(H)}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2\min \{d_t(G),d_t(H)\}$$\end{document} and d(G□H)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d(G \mathbin \square H)$$\end{document} is bounded below by 2min{d(G),dt(H)}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2\min \{d(G),d_t(H)\}$$\end{document}. As a consequences, we get new bounds for the domatic and total domatic number of hypercubes and Hamming graphs of certain dimensions, and exact values for some n-dimensional tori which turns out to be a generalization of a result due to Gravier from 2002.