×

Relating pairs of distance domination parameters. (English) Zbl 0830.05039

The concepts of independence number, domination number and total domination number are generalized. A set \(D\) of vertices of a graph \(G\) is \(n\)-dominating (or total \(n\)-dominating), if every vertex of \(V(G)- D\) (or of \(V(G)\) respectively) has distance at most \(n\) from at least one vertex of \(D\) other than itself. The minimum number of vertices of an \(n\)-dominating (or total \(n\)-dominating) set in \(G\) is the \(n\)-domination number \(\gamma_n(G)\) (or total \(n\)-domination number \(\gamma^t_n(G)\)) of \(G\). A set \(I\) of vertices of \(G\) is \(n\)-independent, if the distance between two arbitrary vertices of \(I\) in \(G\) is at least \(n+ 1\). The minimum number of vertices of a maximal (with respect to set inclusion) \(n\)-independent set in \(G\) is the \(n\)-independence number \(i_n(G)\) of \(G\). Some inequalities relating these concepts are presented. A condition for the equality \(\gamma_n(G)= i_n(G)\) is stated.

MSC:

05C35 Extremal problems in graph theory
05C12 Distance in graphs
PDFBibTeX XMLCite