×

Relationships between distance domination parameters. (English) Zbl 0801.05038

Some numerical invariants of graphs are generalized. Let \(n\) be a positive integer. A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called \(P_{\leq n}\)-dominating (or total \(P_{\leq n}\)-dominating) if each vertex of \(V(G)- D\) (or of \(V(G)\) respectively) has distance at most \(n\) from some vertex of \(D\). A subset \(I\) of \(V(G)\) is called \(P_{\leq n}\)- independent, if any two distinct vertices of \(I\) have distance at least \(n\). Using these definitions, the \(P_{\leq n}\)-domination number \(\gamma_ n(G)\), the total \(P_{\leq n}\)-domination number \(\gamma^ t_ n(G)\), the \(P_{\leq n}\)-independence number \(\beta_ n(G)\) and the \(P_{\leq n}\)-independent domination number \(i_ n(G)\) are introduced. Also the \(P_{\leq n}\)-covering number is defined. Some inequalities in terms of these graph invariants are proved.

MSC:

05C35 Extremal problems in graph theory
05C99 Graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: EuDML