2021/03/19 by P. Francis, Francis, P., Deepak Rajendraprasad +1
Computer Science · Mathematics · #05C15 #05C69 #Advanced Graph Theory Research #Bipartite graph #Cartesian product #Combinatorics #Combinatorics (math.CO) #Discrete mathematics #FOS: Mathematics #G.2 #Graph #Graph Labeling and Dimension Problems #Interconnection Networks and Systems #Mathematics #Vertex (graph theory) #acm:05C15 #acm:05C69 #math.CO #msc:05C15 #msc:05C69
paper · pdf · doi:10.48550/arxiv.2103.10713
published in arXiv (Cornell University) (Cornell University) · 17 Pages
arxiv created 2021/03/19 · openalex publication_date 2021/03/19 · arxiv updated 2021/03/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A domatic (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 (neighborhood). The domatic (total domatic) number of G, denoted d(G) (dt (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 G \cart H is bounded above by max\|V(G)|, |V(H)|\ and below by max\d(G), d(H)\. Both these bounds are tight for an infinite family of graphs. Further, we show that if H is bipartite, then dt(G \cart H) is bounded below by 2min\dt(G),dt(H)\ and d(G \cart H) is bounded below by 2min\d(G),dt(H)\. These bounds give easy proofs for many of the known bounds on the domatic and total domatic numbers of hypercubes \citechen,zel4 and the domination and total domination numbers of hypercubes \citehar,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 \mathop\carti=1n Cki with some suitable conditions to each ki, which turns out to be a generalization of a result due to Gravier \citegrav2 %[Total domination number of grid graphs, Discrete Appl. Math. 121 (2002) 119-128] and give easy proof of a result due to Klavžar and Seifter \citesand.