DOMATIC NUMBER OF GENERALIZED PETERSEN GRAPHS

In a graph G a vertex v dominates itself and its neighborhood. A domatic partition in a graph G is a partition of V (G) into pairwise disjoint dominating sets. The domatic number d(G) of G is the maximum cardinality of a domatic partition of G. A generalized Petersen graph, denoted by P(n,k), is obtained by letting is vertex set be {u1, ..., un} ﾚ {v1, ..., vn} and its edge set be {uiui+1, uivi, vivi+1}; where i=1, ..., n and subscripts are reduced modulo n. In this talk forst we characterize generalized Petersen graphs with maximum domatic number 4, then we study domatic number of P(n,k) for kΞ0 (mod3) or nΞ0 (mod3). Also we determine domatic number of P(n,k) for 3lk ≤ n ≤ 3l (k+1) and P(n,1).

کلیدواژه ها:

Domatic number ، Generalized Petresen graph