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. Alfaro1, Christian Rubio-Montiel2 and Adrián Vázquez Ávila3,
1Banco de México, Ciudad de México, México; carlos.alfaro@banxico.org.mx
2Divisió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
3Subdirecció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, β(G), and a new parameter associated to G, which is called 2-degree-packing number of G, ν2(G). We prove that ν2(G)/2β(G)ν2(G)1, for any simple graph G, with |E(G)|>ν2(G). Also, we give a characterization of connected graphs that attain the equalities.

Keywords:

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