Similarities and Differences Between the Vertex Cover Number and the Weakly Connected Domination Number of a Graph
Magdalena Lemańska, Juan Alberto Rodriguez-Velazquez, Rolando Trujillo-Rasúa · Fundamenta Informaticae · 2017
A vertex cover of a graph G = ( V, E) is a set X ⊂ V such that each edge of G is incident to at least one vertex of X. The vertex cover number τ( G) is the minimum cardinality of a vertex cover of G. A dominating set D ⊆ V is a weakly connected dominating set of G if the subgraph G[ D] w = ( N[ D], E w ) weakly induced by D, is connected, where E w is the set of all edges having at least one vertex in D. The weakly connected domination number γ w ( G) of G is the minimum cardinality among all weakly connected dominating sets of G. In this article we characterize the graphs where γ w ( G) = τ( G). In particular, we focus our attention on bipartite graphs, regular graphs, unicyclic graphs, block graphs and corona graphs.