Small Edge Dominating Sets of Regular Graphs
William Duckworth · Electronic Notes in Theoretical Computer Science · 2004
An edge dominating set F of a graph G is a subset of E(G) such that every edge in E(G)⧹F is incident with at least one vertex that is an end-point of an edge in F. 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.