Covering and 2-degree-packing numbers in graphs

Author(s): Carlos A. Alfaro1, Christian Rubio-Montiel2, Adrián Vázquez Ávila3
1Banco de México, Ciudad de México, México
2División de Matemáticas e Ingeniería, FES Acatlán, Uiversidad Nacional Autónoma de México, Ciudad de México, México
3Subdirección de Ingeniería y Posgrado, Universidad Aeronáutica en Querétaro, Querétaro, México
Copyright © Carlos A. Alfaro, Christian Rubio-Montiel, 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.

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.