Small Edge Dominating Sets of Regular Graphs | Zendy

William Duckworth | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Small Edge Dominating Sets of Regular Graphs

Author(s) -

William Duckworth

Publication year - 2004

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2003.12.005

Subject(s) - combinatorics , dominating set , mathematics , vertex (graph theory) , discrete mathematics , edge cover , random regular graph , graph , cardinality (data modeling) , line graph , 1 planar graph , computer science , data mining

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, d3. 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.3 page(s

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research