On Domatic and Total Domatic Numbers of Cartesian Products of Graphs

被引:0
|
作者
P. Francis
Deepak Rajendraprasad
机构
[1] VIT-AP University,Department of Mathematics, SAS
[2] Indian Institute of Technology Palakkad,Department of Computer Science
关键词
Cartesian product; Domatic number; Hamming graph; Torus; Total domatic number; 05C15; 05C69;
D O I
暂无
中图分类号
学科分类号
摘要
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.
引用
收藏
相关论文
共 50 条
  • [31] EDGE DOMATIC NUMBERS OF COMPLETE N-PARTITE GRAPHS
    HWANG, SF
    CHANG, GJ
    GRAPHS AND COMBINATORICS, 1994, 10 (03) : 241 - 248
  • [32] Domatic partitions of computable graphs
    Jura, Matthew
    Levin, Oscar
    Markkanen, Tyler
    ARCHIVE FOR MATHEMATICAL LOGIC, 2014, 53 (1-2) : 137 - 155
  • [33] On the domatic and the total domatic numbers of the 2-section graph of the order-interval hypergraph of a finite poset
    Bouchemakh, Isma
    Ouatiki, Saliha
    DISCRETE MATHEMATICS, 2009, 309 (11) : 3674 - 3679
  • [34] On the {k}-domatic number of graphs
    Aram, H.
    Sheikholeslami, S. M.
    Volkmann, L.
    UTILITAS MATHEMATICA, 2016, 100 : 309 - 322
  • [35] TREE DOMATIC NUMBER IN GRAPHS
    Chen, Xue-gang
    OPUSCULA MATHEMATICA, 2007, 27 (01) : 5 - 11
  • [36] Domatic partitions of computable graphs
    Matthew Jura
    Oscar Levin
    Tyler Markkanen
    Archive for Mathematical Logic, 2014, 53 : 137 - 155
  • [37] Total k-Domatic Partition on Some Classes of Graphs
    Lee, Chuan-Min
    2016 INTERNATIONAL COMPUTER SYMPOSIUM (ICS), 2016, : 74 - 79
  • [38] k-TUPLE TOTAL RESTRAINED DOMINATION/DOMATIC IN GRAPHS
    Kazemi, A. P.
    BULLETIN OF THE IRANIAN MATHEMATICAL SOCIETY, 2014, 40 (03): : 751 - 763
  • [39] The domatic number of regular graphs
    Dankelmann, P
    Calkin, N
    ARS COMBINATORIA, 2004, 73 : 247 - 255
  • [40] Total k-Domatic Partition on Some Classes of Graphs
    Lee, Chuan-Min
    UTILITAS MATHEMATICA, 2018, 109 : 29 - 43