On domination and 2-degree-packing numbers in graphs

Subdirección de Ingeniería y Posgrado, Universidad Aeronáutica en Querétaro, Parque Aeroespacial de Querétaro, 76278 Querétaro, México

^* Corresponding author: adrian.vazquez@unaq.mx

Received: 29 June 2023
Accepted: 2 December 2023

Abstract

A dominating set of a graph G is a set D ⊆ V (G) such that every vertex of G is either in D or is adjacent to a vertex in D. The domination number of G, γ(G), is the minimum order of a dominating set. The domination number has become an interesting research study on several kinds of graphs, and there are many papers related to this parameter and several variants of it. In this paper, we prove that any simple graph G with no isolated vertices satisfies γ(G) ≤ ν₂(G) − 1, where ν₂(G) is the maximum order of a subset R of edges of G such that any three edges from R do not have the same incident vertex. This new parameter is called the 2-degree-packing of G and it is studied in a more general context but with a different name as 2-packing number, see Araujo-Pardo et al. [Util. Math. 105 (2017) 317–336]. Also, in this paper, we give a characterization of simple connected graphs G satisfying γ(G) = ν₂(G) − 1.