2024/02/07 by Renzo Gómez, Juan Gutiérrez, Gómez, Renzo +1
Computer Science · #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2
paper · pdf · doi:10.48550/arxiv.2402.05088
openalex publication_date 2024/02/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a graph~G, the domination number, denoted by~γ(G), is the minimum cardinality of a dominating set in~G. Dual to the notion of domination number is the packing number of a graph. A packing of~G is a set of vertices whose pairwise distance is at least three. The packing number~ρ(G) of~G is the maximum cardinality of one such set. Furthermore, the inequality~ρ(G) ≤ γ(G) is well-known. Henning et al. conjectured that~γ(G) ≤ 2ρ(G)+1 if~G is subcubic. In this paper, we progress towards this conjecture by showing that~γ(G) ≤ (120)/(49)ρ(G) if~G is a bipartite cubic graph. We also show that γ(G) ≤ 3ρ(G) if~G is a maximal outerplanar graph, and that~γ(G) ≤ 2ρ(G) if~G is a biconvex graph. Moreover, in the last case, we show that this upper bound is tight.