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-odam2023.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
Copyright © 2024 Carlos A. Alfaro, Christian Rubio-Montiel and Adrián Vázquez Ávila. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Received: September 29, 2023 – Accepted: December 12, 2024 – Published: February 27, 2024
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.