Header menu link for other important links
X
On Domatic and Total Domatic Numbers of Cartesian Products of Graphs
Published in Springer
2023
Volume: 46
   
Issue: 3
Abstract
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)), 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 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□ H) is bounded below by 2 min { dt(G) , dt(H) } and d(G□ H) is bounded below by 2 min { d(G) , dt(H) } . 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. © 2023, The Author(s), under exclusive licence to Malaysian Mathematical Sciences Society and Penerbit Universiti Sains Malaysia.
About the journal
JournalBulletin of the Malaysian Mathematical Sciences Society
PublisherSpringer
ISSN01266705