AN ALGORITHM TO FIND 2 DISTANCE DOMINATION PARAMETERS IN A GRAPH

Citation
Gh. Fricke et al., AN ALGORITHM TO FIND 2 DISTANCE DOMINATION PARAMETERS IN A GRAPH, Discrete applied mathematics, 68(1-2), 1996, pp. 85-91
Citations number
25
Categorie Soggetti
Mathematics,Mathematics
Volume
68
Issue
1-2
Year of publication
1996
Pages
85 - 91
Database
ISI
SICI code
Abstract
Let n greater than or equal to 1 be an integer and let G be a graph of order p. A set D of vertices of G is a total n-dominating set of G if every vertex of V(G) is within distance n from some vertex of D other than itself. The minimum cardinality among all total n-dominating set s of G is called the total n-domination number and is denoted by gamma (n)(t)(G). A set S of vertices of G is n-independent if the distance ( in G) between every pair of distinct vertices of S is at least n + 1. The minimum cardinality among all maximal n-independent sets of G is c alled the it-independence number of G and is denoted by in(G). In this paper, we present an algorithm for finding a total n-dominating set D and a maximal n-independent set S in a connected graph with at least p greater than or equal to 2n + 1 vertices. It is shown that these set s D and S satisfy the inequality /S/ + n/D/ less than or equal to p. U sing this result, we conclude that if G is a connected graph on p grea ter than or equal to 2n + 1 vertices, then i(n)(G) + n . gamma(n)(t)(G ) less than or equal to p.