## Abstract

The inequality ρ(G)≤γ(G) between the packing number ρ(G) and the domination number γ(G) of a graph G is well known. For general graphs G, there exists no upper bound on γ(G) of the form γ(G)≤f(ρ(G)) where f is a function, as is remarked in [Discrete Math. 309 (2009), 24732478]. In this paper, we observe that γ(G) ≤Δ(G)ρ(G), where Δ(G) denotes the maximum degree of G. We characterize connected graph G with Δ(G)≤3 that achieve equality in this bound. We conjecture that if G is a connected graph with Δ(G)≤3, then γ(G)≤2ρ(G), with the exception of three graphs, one of which is the Petersen graph. We verify this conjecture in the case of claw-free graphs.

Original language | English |
---|---|

Pages (from-to) | 2031-2036 |

Number of pages | 6 |

Journal | Discrete Mathematics |

Volume | 311 |

Issue number | 18-19 |

DOIs | |

Publication status | Published - 6 Oct 2011 |

## Keywords

- Claw-free graph
- Covering
- Domination
- Packing

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics