Abstract | ||
---|---|---|
For a graph G with vertex set V, the total redundance, TR(G), and efficiency, F(G), are defined by the two expressions: TR(G) = min {Sigma(v is an element of S)(1+deg v) : S subset of or equal to V and \N[x]boolean AND S\ greater than or equal to 1 For All x is an element of V}, F(G) = max {Sigma(v is an element of S)(1 + deg v) : S subset of or equal to V and \N[x]boolean AND S\ less than or equal to 1 For All x is an element of V}. That is, TR measures the minimum possible amount of domination if every vertex is dominated at least once, and F measures the maximum number of vertices that can be dominated if no vertex is dominated more than once.We establish sharp upper and lower bounds on TR(G) and F(G) for general graphs G and, in particular, for trees, and briefly consider related Nordhaus-Gaddum-type results. |
Year | Venue | Keywords |
---|---|---|
1999 | ARS COMBINATORIA | upper and lower bounds |
Field | DocType | Volume |
Discrete mathematics,Graph,Combinatorics,Mathematics | Journal | 54 |
ISSN | Citations | PageRank |
0381-7032 | 2 | 0.41 |
References | Authors | |
1 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Wayne Goddard | 1 | 115 | 15.40 |
Ortrud Oellermann | 2 | 12 | 2.51 |
Peter J. Slater | 3 | 593 | 132.02 |
Henda C. Swart | 4 | 160 | 22.54 |