Open Journal of Discrete Applied Mathematics
Vol. 7 (2024), Issue 1, pp. 1 – 10
ISSN: 2617-9687 (Online) 2617-9679 (Print)
DOI: 10.30538/psrp-odam2024.0094

Covering and 2-degree-packing numbers in graphs

Carlos A. Alfaro\(^{1}\), Christian Rubio-Montiel\(^{2}\) and Adrián Vázquez Ávila\(^{3,*}\)
\(^{1}\)Banco de México, Ciudad de México, México; carlos.alfaro@banxico.org.mx
\(^{2}\)División de Matemáticas e Ingeniería, FES Acatlán, Uiversidad Nacional Autónoma de México, Ciudad de México,
México; christian.rubio@acatlan.unam.mx
\(^{3}\)Subdirección de Ingeniería y Posgrado, Universidad Aeronáutica en Querétaro, Querétaro, México;
adrian.vazquez@unaq.mx

Abstract

In this paper, we give a relationship between the covering number of a simple graph \(G\), \(\beta(G)\), and a new parameter associated to \(G\), which is called 2-degree-packing number of \(G\), \(\nu_2(G)\). We prove that \[\lceil \nu_{2}(G)/2\rceil\leq\beta(G)\leq\nu_2(G)-1,\] for any simple graph \(G\), with \(|E(G)|>\nu_2(G)\). Also, we give a characterization of connected graphs that attain the equalities.

Keywords:

2-degree-packing number, Vertex cover, Graph parameters.