Cobertura por vértices mínima em classes de grafos com grau máximo três

Abstract

Given a graph G =(V(G),E(G)), a vertex cover of G consists of a subsetC ⊆V(G) such that, for every edge uv ∈ E(G), either u ∈C or v ∈C. The vertex cover number of a graph G, denoted by τ(G), is the size of a minimum vertex cover of G. In this context, a theoretical study of the vertex cover problem was proposed for the family of snark graphs, defined as cubic, simple, bridgeless graphs that do not admit a proper 3-edge-coloring. The central objective was to investigate the structural properties of these graphs to obtain new bounds for the minimum vertex cover size in the families of Flower snarks, Goldberg snarks, Generalized Blanuša snarks, and Loupekine snarks. Initially, we investigated the Flower snark Fn, determining the parameter τ(Fn) = 2n+1. This result was based on the duality between the minimum vertex cover and the maximumindependent set. Regarding the Goldberg snarks Gn, we established that τ(Gn)= 9n 2 . The proof relied on the decomposition into disjoint subgraphs and the graph’s structure, which is composed of induced odd cycles for which well-defined bounds already exist in the literature. For the first family of Generalized Blanuša snarks, B1 n, we obtained τ(B1 n) = 14n+17 3 . Inaddition to utilizing induced cycles and the existence of disjoint subgraphs, the analysis was based on the structural properties of the graph, exploring the periodicity of its blocks to identify a valid cover pattern. Finally, for the Loupekine snarks Ln (based on LP0 and LP1 with direct-cross edges), the parameter was fixed at τ(Ln) = 4n. This value was obtained primarily through the analysis of the induced C5 cycles present in the graph structure.