Opuscula Math. 27, no. 1 (2007), 5-11

Opuscula Mathematica

# Tree domatic number in graphs

Xue-gang Chen

Abstract. A dominating set $$S$$ in a graph $$G$$ is a tree dominating set of $$G$$ if the subgraph induced by $$S$$ is a tree. The tree domatic number of $$G$$ is the maximum number of pairwise disjoint tree dominating sets in $$V(G)$$. First, some exact values of and sharp bounds for the tree domatic number are given. Then, we establish a sharp lower bound for the number of edges in a connected graph of given order and given tree domatic number, and we characterize the extremal graphs. Finally, we show that a tree domatic number of a planar graph is at most $$4$$ and give a characterization of planar graphs with the tree domatic number $$3$$.

Keywords: tree domatic number, regular graph, planar graph, Cartesian product.

Mathematics Subject Classification: 05C69, 05C35.

Full text (pdf)

• Xue-gang Chen
• North China Electric Power University, Department of Mathematics, Beijing 102206, China