Domination and packing in graphs

Gómez R.; Gutiérrez J. · Discrete Mathematics (2025) · DOI: 10.1016/j.disc.2025.114393

Resumen

Given a graph G, the domination number γ(G) is the minimum cardinality of a dominating set in G, and the packing number ρ(G) is the minimum cardinality of a set of vertices whose pairwise distance is at least three. The inequality ρ(G)≤γ(G) is well-known. Furthermore, Henning et al. conjectured that γ(G)≤2ρ(G)+1 if G is subcubic. In this paper, we show that [Formula presented] if G is a bipartite cubic graph. This result is obtained by showing that [Formula presented] for this class of graphs, which improves a previous bound given by Favaron. 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, where the latter result is tight.

Instituciones: Universidad de Ingeniería y Tecnología