An edge dominating set ? of a graph G is a subset of E(G) such that every edge in E(G)\? is incident with at least one vertex that is an end-point of an edge in ?. Edge dominating sets of small cardinality are of interest. We refer to the size of a smallest edge dominating set of a graph G as the edge domination number of G and denote this by ?(G). In this paper we improve all current known upper bounds on ?(G) when G is a random d-regular graph, d�3. This is achieved by analysing a simple greedy heuristic on random regular graphs using differential equations. Our results compare favourably with known lower bounds on ?(G) when G is a random regular graph.
|Number of pages||3|
|Journal||Proceedings of Computing: The Australasian Theory Symposium (CATS) 2004|
|Publication status||Published - 2004|
|Event||Computing: The Australasian Theory Symposium (CATS) 2004 - Dunedin, New Zealand|
Duration: 19 Jan 2004 → 20 Jan 2004