On the ratios between packing and domination parameters of a graph |
| |
Authors: | Alewyn P Burger |
| |
Institution: | a Department of Logistics, University of Stellenbosch, Private Bag X1, Matieland, 7602, South Africa b School of Mathematical Sciences, University of KwaZulu-Natal, Pietermaritzburg, 3209, South Africa |
| |
Abstract: | The relationship ρL(G)≤ρ(G)≤γ(G) between the lower packing number ρL(G), the packing number ρ(G) and the domination number γ(G) of a graph G is well known. In this paper we establish best possible bounds on the ratios of the packing numbers of any (connected) graph to its six domination-related parameters (the lower and upper irredundance numbers ir and IR, the lower and upper independence numbers i and β, and the lower and upper domination numbers γ and Γ). In particular, best possible constants aθ, bθ, cθ and dθ are found for which the inequalities and hold for any connected graph G and all θ∈{ir,γ,i,β,Γ,IR}. From our work it follows, for example, that and for any connected graph G, and that these inequalities are best possible. |
| |
Keywords: | Graph packing Irredundance Domination Independence Graph parameter ratios |
本文献已被 ScienceDirect 等数据库收录! |
|