Name
Abstract | ||
|---|---|---|
For an orientation G of a simple graph G, N G [x] denotes the vertex x together with all those vertices in G for which there are arcs directed toward x . A set S of vertices of G is an efficient dominating set (EDS) of G provided that IFld | N G [x]∩ S| = 1 for every x in G . An efficiency of G is an ordered pair ( G , S ), where S is an EDS of the orientation G of G . The number of distinct efficiencies of G is denoted is denoted by η ( G ). We give a formula for η ( G ) which allows us to calculate it for complete graphs, complete bipartite graphs, cycles, and paths. We find the minimum and maximum value of η ( G ) among all graphs with a fixed number of edges. We also find the minimum and maximum value of η ( G ), as well as the external graphs, among all graphs with a fixed number of vertices. Finally, we show that the probability a random oriented graph has an EDS is exponentially small when such graph is chosen according to a uniform distribution. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1016/S0012-365X(97)81813-4 | Discrete Mathematics |
Keywords | Field | DocType |
efficient domination,uniform distribution,complete graph,complete bipartite graph,dominating set | Random regular graph,Discrete mathematics,Combinatorics,Graph toughness,Graph power,Bound graph,Cycle graph,1-planar graph,Pancyclic graph,Mathematics,Metric dimension | Journal |
Volume | Issue | ISSN |
178 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
4 | 0.67 | 1 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David W. Bange | 1 | 6 | 2.49 |
| Anthony E. Barkauskas | 2 | 6 | 2.49 |
| Linda H. Host | 3 | 5 | 1.34 |
| Lane H. Clark | 4 | 43 | 9.39 |