Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 43-45 |
| Number of pages | 3 |
| Journal | Proceedings of Computing: The Australasian Theory Symposium (CATS) 2004 |
| DOIs | |
| Publication status | Published - 2004 |
| Event | Computing: The Australasian Theory Symposium (CATS) 2004 - Dunedin, New Zealand Duration: 19 Jan 2004 → 20 Jan 2004 |