A vertex cover of a simple graph G is a subset of vertices S ¿ V (G) which covers all edges, that is, for every pair of adjacent vertices u and v, either u or v belong to S. The minimum size of a vertex cover of G is denoted by ß(G). Let G be a connected simple graph. We say that G is destroyable or trail-coverable if there is a trail P that is vertex cover, if that is the case, we say that P is a covering trail. In particular, when the covering trail may be a path, we say path-destroyable. We...
A vertex cover of a simple graph G is a subset of vertices S ¿ V (G) which covers all edges, that is, for every pair of adjacent vertices u and v, either u or v belong to S. The minimum size of a vertex cover of G is denoted by ß(G). Let G be a connected simple graph. We say that G is destroyable or trail-coverable if there is a trail P that is vertex cover, if that is the case, we say that P is a covering trail. In particular, when the covering trail may be a path, we say path-destroyable. We introduce the parameter ßt(G) as the minimum size of a vertex cover that induces a trail in G. If G is not destroyable we put ßt(G) = 8. Let G be a connected simple graph with girth g(G) = 3 and circumference c(G). We say that a G is circuit-destroyable or circuit-coverable if there is a circuit C in G that is vertex cover of the graph, if that is the case, we say that C is a covering circuit. In particular, when the covering circuit may be a cycle, we say cycle-destroyable. We also introduce the parameter ßc(G) as the minimum size of a vertex cover that induces a circuit in G. If G is not circuit-destroyable we put ßc(G) = 8. In this talk, we will present some minimal graphs, in terms of edges, that are not circuit o trail coverable. We also will study the parameters ßc(G) and ßt(G) for some families of graphs.