Tree domatic number in graphs

• Autorzy: Chen X. G.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

tree domatic number; regular graph; planar graph; Cartesian product

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2007
• Tom: Vol. 27, no. 1
• Strony: 5--11
• Opis fizyczny: Bibliogr. 3 poz.

Twórcy

autor

Chen X. G.

• North China Electric Power University, Department of Mathematics, Beijing 102206, China,

Bibliografia

• [1] B. Zelinka, Connected domatic number of a graph, Math. Slovaca 36 (1986), 387-392.
• [2] B.I. Hartnell, D.F. Rall, Connected domatic number in planar graph. Czechoslovak Math. Journal 51 (126) (2001), 173-179.
• [3] X.G. Chen, L. Sun, A. McRae, Tree domination in graphs, Ars Comb. 73 (2004), 193-203.