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
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, β(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.