Article ID Journal Published Year Pages File Type
4648296 Discrete Mathematics 2011 6 Pages PDF
Abstract

The inequality ρ(G)≤γ(G)ρ(G)≤γ(G) between the packing number ρ(G)ρ(G) and the domination number γ(G)γ(G) of a graph GG is well known. For general graphs GG, there exists no upper bound on γ(G)γ(G) of the form γ(G)≤f(ρ(G))γ(G)≤f(ρ(G)) where ff is a function, as is remarked in [Discrete Math. 309 (2009), 2473–2478]. In this paper, we observe that γ(G)≤Δ(G)ρ(G)γ(G)≤Δ(G)ρ(G), where Δ(G)Δ(G) denotes the maximum degree of GG. We characterize connected graph GG with Δ(G)≤3Δ(G)≤3 that achieve equality in this bound. We conjecture that if GG is a connected graph with Δ(G)≤3Δ(G)≤3, then γ(G)≤2ρ(G)γ(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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,