Small Edge Dominating Sets of Regular Graphs

W Duckworth

Research output: Contribution to journalConference paper

4 Citations (Scopus)

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 languageEnglish
Pages (from-to)43-45
Number of pages3
JournalProceedings of Computing: The Australasian Theory Symposium (CATS) 2004
DOIs
Publication statusPublished - 2004
EventComputing: The Australasian Theory Symposium (CATS) 2004 - Dunedin, New Zealand
Duration: 19 Jan 200420 Jan 2004

Fingerprint Dive into the research topics of 'Small Edge Dominating Sets of Regular Graphs'. Together they form a unique fingerprint.

Cite this