### Abstract

In 1996, Reed proved that the domination number γ(G) of every n-vertex graph G with minimum degree at least 3 is at most 3n/8. Also, he conjectured that γ(H)≤⌈n/3⌉ for every connected 3-regular (cubic) n-vertex graph H. In this note, we disprove this conjecture. We construct a connected cubic graph G on 60 vertices with γ(G)=21 and present a sequence ⌈Gk⌉k=1∞ of connected cubic graphs withlimk→∞γ(Gk)|V(Gk)|≥823=13+169.

Original language | English (US) |
---|---|

Pages (from-to) | 45-50 |

Number of pages | 6 |

Journal | Discrete Mathematics |

Volume | 304 |

Issue number | 1-3 |

DOIs | |

State | Published - Nov 28 2005 |

### Keywords

- Cubic graphs
- Dominating set
- Domination

### ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics

## Fingerprint Dive into the research topics of 'On domination in connected cubic graphs'. Together they form a unique fingerprint.

## Cite this

Kostochka, A. V., & Stodolsky, B. Y. (2005). On domination in connected cubic graphs.

*Discrete Mathematics*,*304*(1-3), 45-50. https://doi.org/10.1016/j.disc.2005.07.005