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

# Tree domatic number in graphs

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.
Xue-gang Chen, Tree domatic number in graphs, Opuscula Math. 27, no. 1 (2007), 5-11

a .bib file (BibTeX), a .ris file (RefMan), a .enw file (EndNote)
or export to RefWorks.

ISSN 1232−9274, e-ISSN 2300−6919, DOI http://dx.doi.org/10.7494/OpMath
Contact: opuscula@agh.edu.pl